A small observation, maybe even trivial:
Viewed over a finite ring (field) of Mp = 2^p - 1 elements the polynomial
x^p - 1 splits (completely, of course) into linear factors of the form (x -
2^r) for 0 <= r <= p-1.
Alternatively, x^p - 1 = (x-1)(x-2)(x-4)(x-8)(...)[ x - 2^(p-1)] (mod Mp)
As a buddy once asked, "So what?" I rarely had a good answer for him and I
do not have one now.
Joth
----- Original Message -----
From: <[EMAIL PROTECTED]>
To: <[EMAIL PROTECTED]>
Sent: Friday, July 23, 1999 11:36 AM
Subject: Mersenne: Re: p-1 algorithm
> Lucas Wiman wrote, about the p-1 algorithm:
>
> >What if we use 2 as a base?
>
> Unfortunately, 2 is not an eligible base for the powering.
>
> Example: let's attempt to factor 2^11 - 1 = 23*89 via p-1. The smaller
> factor has p-1 = 22=2*11, so raising the base to the powers 2 and 11
> and gcd'ing should reveal the factor. Let's denote the product of the
> small primes used for the powering by #, and try bases A = 2 and 3:
>
> A=2: 2^22 mod M11 = (2^11)^2 mod M11 == 1. You can continue to power until
> you're blue in the face, and all you'll ever get is one, i.e. gcd(a^#-1,
M11)
> = 0.
>
> A=3: 3^22 mod M11 = 1013, so gcd(a^#-1, M11) = gcd(1012,2047) = 23.
>
> For Mersennes you can in fact use any base you like, as long as it's not
> a power of 2.
>
> EXERCISE: We wish to attempt to find an odd prime factor p of a number N
> via the p-1 method. What is the mathematical requirement for A to be an
> eligible base for the powering?
>
> EXERCISE: which movie is the following quote from?
>
> "...and three shall be the number of the counting. Four shalt thou not
count,
> nor two, excepting thou then proceed to three. Five is right out..."
>
> -Ernst
> _________________________________________________________________
> Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
> Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
>
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
