2
$\begingroup$

EDIT 2011.05.09 Thanks to Junkie and Tapio Rajala for checking on me. While most of the candidates referred to below have small factors, the "large" small factors I list below are incorrect. Also, that $2^{2557} - 2^{1278} + 1$ does not have a small factor supports my "feeling" that the candidate set should have not so many small factors as I was seeming to find. I apologize for submitting such false suggestions to MathOverflow. (This post will teach me to double check my work before posting, cautious language notwithstandng.) Further updates (if any) will be near the end of this post. END EDIT 2011.05.09

Following this answer to a question of Luis Gallardo, I set my computer to look for small factors. After looking through a lot of primes, my computer suggests that $223381441$ divides $2^{2557} - 2^{1278} + 1$ and that $234355951$ divides $2^{121} - 2^{60} + 1$. The remaining exponent to be cracked is $132049$ (find a nontrivial factor or establish primality of $2^{264097} - 2^{132048} + 1$). Given that the initial candidate set was based on the $47$ known perfect numbers and that the largest of the smallest factors of all but one of them is $2^{37} - 2^{18} + 1$ (meaning that the perfect number with Mersenne exponent $19$ precedes a prime), how can I use this information to determine how likely it is that the remaining candidate has a small ($< 2^{32}$) prime factor?

(If you have a bignum package and want to do a few primality tests, I would receive that information. I would also appreciate independent verification that $42$ of the $47$ candidates are composite with small prime factors. Currently I am using 32-bit arithmetic and the moral equivalent of trial factorization to determine primality of these candidates. In spite of my initial observations that $7$ or $11$ divide most of the candidates, I am surprised at my success so far in finding small prime factors. Or should I be? That is the point of this question.)

(Also, to answer Luis's question, at this point I'd say about four or five.)

EDIT 2011.07.14 After running for several weeks, the program I had to find small prime factors finished. The major bug it had involved roundoff error, and so reported several factors which turned out not to be factors, including the two reported above and challenged (and correctly so) by Junkie.

I am independently attempting to check the factorization using the Elliptic Curve Method of $2^{2557} - 2^{1278} + 1$; that's on its 17th day currently after several restarts of the computer doing the calculations.

In addition to Charles's answer below, one can look at Hans Riesel's book Prime Numbers and Computer Methods for Factorization. The book has sections on Dickman's Theorem and on the work of Knuth and Trabb-Pardo on how prime factors are distributed according to size. END EDIT 2011.07.14

Gerhard "Ask Me About System Design" Paseman, 2011.05.06

Improve this question
$\endgroup$
12
  • 1
    $\begingroup$ So, Gerhard, do you know how to design a bignum system? ... couldn't resist ^_^ $\endgroup$
    – user5810
    May 7, 2011 at 6:57
  • $\begingroup$ With PFGW: 2^264097 - 2^132048 + 1 is composite: RES64: [1B3B60AEC3578817] (851.5764s+250.7794s) $\endgroup$
    – Tapio Rajala
    May 7, 2011 at 9:16
  • $\begingroup$ I verified that the other 42 candidates all have small factors (with PFGW). $\endgroup$
    – Tapio Rajala
    May 7, 2011 at 9:56
  • $\begingroup$ Just to make the verification faster: $2^{264097} - 2^{132048} + 1$ has a factor $194528547122653$. $\endgroup$
    – Tapio Rajala
    May 7, 2011 at 14:01
  • 1
    $\begingroup$ "my computer suggests that 223381441 divides $2^{2557}−2^{1278}+1$..." except this is not true?? For $2^{121}-2^{60}+1$, the smaller cofactor is $2432582681$, not the $234355951$ you suggest. $\endgroup$
    – Junkie
    May 7, 2011 at 20:49

1 Answer 1

Reset to default
1
$\begingroup$

232 is fairly small, so the easiest way to determine if the number has a prime factor up to that size is probably just to trial divide. I just did that in GP:

test(p)=my(two=Mod(2,p));two^264097-two^132048+1;
forprime(p=2,1<<32,if(!test(p),return(p)))

(actually, I used a customized function rather than forprime() but that makes little difference here) and found that it does not. The calculation took 10 minutes on a heavily-loaded Phenom II.

Generally to determine the chance of finding a prime factor I would use Mertens' theorem to find the expected number of prime factors in a given range then use negative binomial/Poisson to determine probabilities.

Improve this answer
$\endgroup$
6
  • 1
    $\begingroup$ Did you use the variable p for two different things for any reason other than obfuscation? $\endgroup$
    – Kevin Buzzard
    May 7, 2011 at 12:14
  • $\begingroup$ Thank you. What is your opinion on the result? Is it suprising to find as many small factors as occurred for a set like this? (My program still has not tried primes above 2^29.) Gerhard "Ask Me About System Design" Paseman, 2011.05.07 $\endgroup$
    – Gerhard Paseman
    May 7, 2011 at 17:04
  • $\begingroup$ Also, could you explain your test? The code doesn't look like it is doing trial division. Gerhard "Ask Me About System Design" Paseman, 2011.05.07 $\endgroup$
    – Gerhard Paseman
    May 7, 2011 at 17:22
  • $\begingroup$ Gerhard: it's just trial division but with the added complication that p means two different things. $\endgroup$
    – Kevin Buzzard
    May 7, 2011 at 20:26
  • $\begingroup$ Maybe someone should edit the code (and add a new variable q) to remove that ambiguity. $\endgroup$
    – André Henriques
    May 7, 2011 at 22:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.