I know about the quadratic reciprocity trick for filtering out half the candidates (i.e., in the case of Mersenne numbers, it amounts to the "1 or 7 (mod 8)" condition) but haven't implemented it yet. There's a lot of potential for improvement left, the code is more or less an one afternoon hack to get some kind of trial factoring code running.

Alex

[QUOTE=Zeta-Flux;87203]
Also, each of the exponents is prime, so you don't have to worry about algebraic factors.[/QUOTE]

Why you don't see algebraic factors??? Because it has got high possibility for some numbers that for example 151^2351+-1 hasn't got "small factors", but 151^(2*3*2351)-1 has got some small prime factors that are different from prime factors of 151^6+-1. So for this for ECM the best way to check phi(2351,151), phi(2*2351,151),phi(3*2351,151),phi(6*2351,151).

Or check prime divisors of phi(n,b) by trial divison, all divisors are in the form k*b+1.

Another thing. It would be good to list all known factors of b^n-1: like this:

233^(2*3*773*18701)-1 is divisible by:
2^4
3^3
7
13
29
37
487
7789
112207
177791
919871
6171331
24909733
13199749
86735239^2
467971109
699824729
954087619
3035733331
32965234321
219960563569
(perhaps there are other missed small primefactors)

This number is still on Oddperfect page. Not bad 21 different prime factors. If you want to prove say an oddperfect number has got at least 10 prime factors then that can't be divisible by this number. Anyway I like silly projects.

Zeta-Flux, why are we seeing numbers that can't be sigma factor values of an odd perfect numbers? If b^n-1 in your examples is divisible by 4, then from sigma(N)=2*N this is a contradiction: since sigma is a multiplicative function and b(k*n)-1 is divisible by b^n-1 so b^(k*n) and also sigma(n) is divisible by 4, this is a contradiction, because 2*N isn't divisible by 4.

[QUOTE=frmky;87217]All of the factors that I have submitted were found by trial division. Remember that large factors of a^n-1 are of the form kn+1 for some k. For example,
567696479734193399 | 587^634331767 - 1
567696479734193399 = 894951994 * 634331767 + 1

The program I created is quite simple. It just uses a powermod function to find a^n % (kn+1) for each odd kn+1. Using it, I searched each of the remaining numbers to k = 3.4 billion.

Greg[/QUOTE]Fair comment.

However, trial division isn't going to get very far without a [b]lot[/b] of effort.

Paul

[QUOTE=xilman;87209]Note that the ones with very large exponents, with more than 5 digits, say, are not feasible candidates for anything other than trial division. The numbers are just too large otherwise.

I don't yet have a good program to perform TD on those numbers. I may yet write one, but no promises. Even then, finding factors >10^10 will be very hard and quite probably infeasible. For instance, I see no plausible way of factoring the penultimate number on your list. The exponent is just too big.

I'll start on the ones with exponent < 10000.


Paul[/QUOTE]Desite some difficulties (including, perhaps, discovering a bug in ecm-gmp) I've made a start on the numbers with under 100K digits.

The first pass, now complete, was to identify all tiny factors. Two larger ones were found but, at p10 and p11, aren't quite large enough.


Paul

R. Gerbicz,
please see posts 77 to 80

Akruppa,
thank you for the program.
It seems that factorcyc assumes that parameter <start> is 1 (mod b).
Adding "add_for_congruence (mstart, 1, 1, b);"
after "mpz_set_str(mstart, argv[3], 10);"
is a cheap way to fix it.

>It seems that factorcyc assumes that parameter <start> is 1 (mod b).

Correct. Sorry, I should have pointed that out.

Alex

[QUOTE=frmky;87217]
Remember that large factors of a^n-1 are of the form kn+1 for some k.[/QUOTE]

That's not true!
Correctly: if n is a prime number then all prime divisors of (a^n-1)/(a-1) are in the form k*n+1.
Or in general: prime factors of phi(n,b) are in the form k*n+1.

[QUOTE=Pascal Ochem;87323]R. Gerbicz,
please see posts 77 to 80
[/QUOTE]

Great! I haven't seen them.

xilman,

Thanks for your efforts. If you found a bug in ECM-GMP that'd be cool. During my calculations with Mathematica 5.2, I found a bug in their "factorinteger" command. It is probably things like these (along with the enjoyment of trying to solve a VERY old problem) that make the project worthwhile.

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

R. Gerbicz,

I appreciate your earlier suggestion for my paper. The paper has been accepted by Math. Comp., and I don't really feel comfortable changing it too much (I will change "43 found Mersenne primes" to 44 though!), so I probably won't add that sentence. I think most readers can puzzle through it and figure out what happens if p>10^13.

Also, in your last post, your result is still slightly incorrect. You have to worry about n|(a^n-1)/(a-1), if n is prime, and n|(a-1). But, in spirit, the factors of a^n-1 one deals with are kn+1.

You also asked why we didn't see more algebraic factors in xilman's list. This was simply to simplify the list of integers I gave to him. It appeared that he was just going to jump into ECM, and in that case the smallest (nontrivial) algebraic factor would do the best.

Finally, I think I answered your other questions when I responded to other's posts earlier in the thread.

Best wishes,
Pace Nielsen

[QUOTE=Zeta-Flux;87329]You also asked why we didn't see more algebraic factors in xilman's list. This was simply to simplify the list of integers I gave to him. It appeared that he was just going to jump into ECM, and in that case the smallest (nontrivial) algebraic factor would do the best.[/QUOTE]

Yup. As I said when I first offered: I didn't want to have to think much about what I need to do. Under my present circumstances, computing time costs me much less than thinking time.


I'm getting useful results now. Several more p11 (which aren't useful) and a p13 and p19 which are. They are both of the same number too!


More details when the present ECM run finishes.


Paul

[QUOTE=xilman;87332]Several more p11 (which aren't useful) [/QUOTE]

Send those along, too. I've been thinking that someday somebody is going to be interested in more thorough factorization of Vanishing Fermat Quotients, so I'm tracking other factors that are not useful to Pace, too.