Factorization on 2^p +1

[CRGreathouse]

Originally Posted by jyb

I guess that depends on what "the question" is here. From the quotes above, I thought that Bob was suggesting that any number theory book would contain what was required to understand "that fractional mod stuff." And I was pointing out that the book which William mentioned did indeed appear to have that. If I misunderstood the actual question being raised then I apologize.

No need to apologize, now we know what you and Bob meant so everyone is on the same page.

[only_human]

Originally Posted by CRGreathouse

No need to apologize, now we know what you and Bob meant so everyone is on the same page.

I'm also tracking on the same page now; I imagine that this brief excursion might clear the cobwebs for anyone else reading the thread who finds themself in a rusty or ill-equipped boat. Thank you for the link wblipp.

[Raman]

Originally Posted by kurtulmehtap

Hi All,
We know the factors of 2^p -1 are in the form 2kp +1, What about
Factors of 2^p +1? Do they have a special form and what is the fastest way to find the factors?
Thanx

SNFS is the fastest way to find out the factors. Factors of special form, that is one of the reasons why I began to like that Cunningham project. Factors always of form 2kp+1 for prime exponents, derived algebraic factors for composite exponents, Aurifeuillian factorizations, these also hold good for that Fibonacci/Lucas numbers, homogeneous Cunningham numbers as well. Now that (recently only) actually I came to know that if the base is prime, then every factor of Cunningham number will be order of subfield of GF(bⁿ).

The best way to visualize that factors of form 1 (mod p) for Mersenne numbers (with prime exponents) is that
The order of element 2 over Z_q* is equal to p, if some prime q divides with that Mersenne number 2^p-1.
By theory, the order of element 2 over Z_q* is a divisor of q-1 (it is equal to q-1 if in case that 2 is a generator), so that q should be chosen in a way such that q-1 is a multiple of p.

For Fermat Numbers, if some prime q divides with that 2^2[sup]n[/sup]+1, then order of q is exactly 2ⁿ⁺¹, since 2^2[sup]n[/sup] is congruent to -1 (mod q). The group order of that element 2 should also be a divisor of q-1, that is equal to 2ⁿ⁺¹ exactly.

Further that when n is greater than (or equal to) 2, then that prime q (by using that above conditions) should be of the form 1 (mod 8), so that the element 2 will then be a quadratic residue (mod q), thus its group order should be a divisor of (q-1)/2 as well.

--------------------------------------------------------------------------

With current computing resources of NFS@Home, each linear algebra (matrix) took only upto 2 days, but that I saw that 3,563+ has been staying up within the post-processing stage for atleast 5 days. Why is it so, thus?

--------------------------------------------------------------------------

Originally Posted by jasonp

We had one spammer register with a username that contained a strange character in it; the forum software could display it but it could not be copy-and-pasted into text boxes. Xyzzy had to manually ban him via SQL :)

May I know what that special character is, atleast the full user name, or that user ID if that is possible? Post over here, or just simply PM me, if in case that if you want to hide that information from others as well.

[jasonp]

Originally Posted by Raman

With current computing resources of NFS@Home, each linear algebra (matrix) took only upto 2 days, but that I saw that 3,563+ has been staying up within the post-processing stage for atleast 5 days. Why is it so, thus?

We get a quota of CPU hours for using the big clusters, and until Greg's grant proposal is granted the temporary quota we have now just sufficient to complete the LA for 5,409-. So for smaller jobs he's using a small local cluster. 3,563+ should be done in a few days.

May I know what that special character is, atleast the full user name, or that user ID if that is possible? Post over here, or just simply PM me, if in case that if you want to hide that information from others as well.

It was long enough ago that the logs have been deleted.