Existe-t-il un moyen de désigner X dans y = (k1 + k2 × x) mod (s)?

J'écris un programme dans C# qui doit trouver X où le plus grand commun diviseur de k2 et s est 1, x est plus petit que s et k1, k2, y, s sont des constantes. À l'heure actuelle, je le fais en mettant toutes les valeurs de X à zéro et en vérifiant si elles ont raison, mais cela prend beaucoup de temps quand j'ai plus de 40000 valeurs. Ou si c'est plus facile pour vous, vous pouvez essayer de désigner X à partir de y = x mod (s).Existe-t-il un moyen de désigner X dans y = (k1 + k2 × x) mod (s)?

Il y a un code J'utilise en ce moment pour le résoudre:

if (GCD(k2, k) == 1) 
     { 
      for (int i = 0; i < k; i++) 
      { 
       n1 = 0; 
       n = 0; 
       while(n < 1) 
       { 
        if(i == (k1 + k2 * n1) % k){ 
         s1[n1] = s[i]; 
         n++; 
        } 
        n1++; 
       } 
      } 
     }

Merci à l'avance.

P.S. Si quelque chose ne sait pas, alors laissez-moi savoir, il est un peu difficile pour moi d'expliquer tout cela: P

Source

2017-01-30 Jakub Sobierski

Vous voulez trouver le plus grand nombre que les deux nombres peuvent diviser? par exemple 4 pour 12 et 20? –

Pouvez-vous donner un exemple numérique avec des solutions que vous connaissez? Quelles sont les valeurs typiques de y, k1, k2, s et x? –

Indice: Savez-vous ce qu'est un * multiplicatif inverse *? –

Parcourons un exemple de problème:

Solve for X: 
17395 = (100 + 43 * X) % 633424

Démarrer en éliminant l'ajout:

17395 - 100 = (43 * X) % 633424 
17294 = (43 * X) % 633424

maintenant, supposons qu'il existe un certain nombre y tel que

1 = (Y * 43) % 633424

(en plus: Comment pouvons-nous kn ow que Y existe? Il existe ssi 43 et 633424 sont coprime, ce qu'ils sont. C'est un cas particulier de l'identité de Bézout.)

Y est l'inverse multiplicatif de 43 par rapport à 633424.

Comment cela vous aide-t-il? On peut multiplier les deux côtés par 17294:

17294 = (Y * 43 * 17294) % 633424

Et maintenant, nous pouvons lire sur notre solution: X est Y * 17294. Ainsi, le problème se réduit au calcul de l'inverse multiplicatif. Pouvez-vous voir comment trouver un nombre Y tel que 1 = (Y * 43) % 633424? Si vous pouvez trouver ce nombre, vous pouvez trouver X.

Vous pouvez utiliser l'algorithme d'Euclide pour trouver rapidement l'inverse multiplicatif. Voir https://en.wikipedia.org/wiki/Modular_multiplicative_inverse ou ma page sur le sujet https://ericlippert.com/2013/11/12/math-from-scratch-part-thirteen-multiplicative-inverses/

Source

2017-01-30 21:29:55

Existe-t-il un moyen de désigner X dans y = (k1 + k2 × x) mod (s)?

Répondre

Questions connexes