1
$\begingroup$

I'm very curious about this cause I saw it done, but can't understand how and here it goes:

PrimeNumber * SomeNumber % 26

Now if I know the prime number, and the 26 And the result, can I find the "SomeNumber"? Thanks

Edit: I'm not good with math, so a simple explanation without fancy symbols would be appreciated.

  • 0
    So can you spell that out for me as an answer?2012-11-08

1 Answers 1

1

In general, if $\gcd(a,m)=1$, then $ax\equiv b\pmod m$ has a unique solution $x$ satisfying $1\le x\le m$, and this solution can be computed efficiently by use of the extended Euclidean algorithm, which see.

In your situation, where $m=26$, and $a$ is a prime number, the condition $\gcd(a.m)=1$ is guaranteed, unless $a=2$ or $a=13$.