vendredi 2 septembre 2016

Given a prime number P . Find for each 0<= x < P , a corresponding y such that (x*y) % P == 1

I am given a Fixed Prime Number P.

Now, for each X from 0 to P-1, I need to find a corresponding Y such that (X*Y)%P == 1.

Also Y should be from 0 to P-1.

I am thinking in the direction of fermat's little theorem.

Actually, The problem needed to find all Yj such that (Xi*Yj)%P == 1 for each Xi.

But i deduced that for each X there is only 1 possible corresponding Y from 0 to P-1.

Example: Lets P be 5.

Now Xi can be 0,1,2,3,4.

For X=2, We have corresponding Y as 3 as (2*3)%5=1.

For X=4, We have corresponding Y as 4 as (4*4)%5=1.

For X=3, We have 2 as Y.

For X=1, We have Y as 1.

I somehow am unable to figure out the way to calculate Y for each X.

Any Direction is appreciated.

Aucun commentaire:

Enregistrer un commentaire