Chris Jefferson <[EMAIL PROTECTED]> writes:
> Just one question / comment.
>
> We want to find 2^p mod n where n is in form 2kp + 1
> If we KNOW 2kp + 1 is prime, then the euler totient fn. of n is 2kp, call
> this T
>
> Also, if a is co-prime to n, a^T=1 mod n
> 2 is obviously co-prime to n, so 2^T=1 mod n
>
> So another way of working out if a factor would be to work out
>
> So if 2kp + 1 is prime, 2^(2kp)=1 mod (2kp + 1)
>
>
> Herein lies my problem:
>
> I know that if p is prime, 'mod p' is a group under muliplication.
> I know that 2*(2^(p-2))=1 mod p
> so 2^(p-2) is the inverse of 2 and only by multilplying by 2^(p-2) can I
> get 1.
>
>
> Now, this implies that for no 0<N<2kp, 2^N=1 mod (2kp + 1)
>
>> so 2^p cannot be 1 mod (2kp + 1)
> ?????
If q (= 2kp + 1 in Chris's notation) is an odd prime,
then 2^(q-1) == 1 (mod q) by Fermat's little theorem.
We are interested in the multiplicative group modulo q.
The order of 2 divides q-1 = 2kp. We check whether this order
(Chris's N) divides p (in which case it must equal p since p is prime).
Check the computations with p = 11 and q = 23.
2 * 2^(p-2) = 2 * 512 = 1024 == 1 (mod 11).
So 512 == 6 (mod 11) is a multiplicative inverse of 2.
How does this prevent 2^11 == 1 (mod 23)?
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
