mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Lone Mersenne Hunters (https://www.mersenneforum.org/forumdisplay.php?f=12)
-   -   Found a factor, sunshine? Embalm and entomb it here! (RU "Выкрасить и выбросить")) (https://www.mersenneforum.org/showthread.php?t=13977)

rajula 2011-01-15 16:33

[QUOTE=drh;246541]
M51443083 has a factor: 25320591696138535897675469195834877349466521
[/QUOTE]

25320591696138535897675469195834877349466521 = 857285347808257713679 x 29535780310340488803799

[QUOTE]
I'm also assuming that this is composite since it is so large. I'm still very new at this, and learning. Can you tell me what you are doing, or using to tell if these numbers are composite or not?
[/QUOTE]

One easy way is to use [url]http://www.alpertron.com.ar/ECM.HTM[/url].

Mr. P-1 2011-01-15 23:39

[QUOTE=drh;246541]Can you tell me what you are doing, or using to tell if these numbers are composite or not?[/QUOTE]

A really neat trick is to use the P+1 method with the same bounds as the original P-1 test. This has a 50% chance per run of resolving the two factors, and will usually do so in a fraction of the processor time that other methods would take.

[code]$ echo "25320591696138535897675469195834877349466521" | ecm -c 0 -pp1 60000
GMP-ECM 6.2 [powered by GMP 4.2.2] [P+1]
Input number is 25320591696138535897675469195834877349466521 (44 digits)
Using B1=60000, B2=19419970, polynomial x^1, x0=2552205880
Step 1 took 88ms
Step 2 took 96ms
Run 2 out of 0:
Using B1=60000, B2=19419970, polynomial x^1, x0=1936717407
Step 1 took 80ms
[factor found by P-1]
********** Factor found in step 2: 857285347808257713679
Found probable prime factor of 21 digits: 857285347808257713679
Probable prime cofactor 29535780310340488803799 has 23 digits
$[/code]

Not that other methods take much processor time, but I think this is a neat 'hack'.

drh 2011-01-16 19:22

Just wanted to thank lorgix, Mr. P-1, and rajula for responding, and getting me started down the path of understanding, as I'm not a mathematician. I'm sure I'll have lots more questions.

Doug

Mr. P-1 2011-01-16 23:13

[QUOTE=drh;246541]Can you tell me what you are doing, or using to tell if these numbers are composite or not?[/QUOTE]

A simple heuristic is, if its size is more than double the TF limits, then it's almost certainly composite. P-1 (to the limits chosen by Prime95) rarely finds prime factors much more than about 100 bits, and rarely finds composite factors less than double the TF limits (since this would imply a missed TF-sized factor.)

The quickest way to [i]prove[/i] these numbers composite would be a PrP test, which wouldn't tell us the prime factors. In practice, we don't bother, because we're interested in the prime factors anyway, and factoring them is so easy. Theoretically, if a large P-1 factor should resist factorisation for any length of time, we might begin to suspect it to be prime after all. To prove a number of that size prime, I'd use Pari/GP's isprime() function. There are several other tools capable of proving much larger numbers prime.

lorgix 2011-01-17 09:19

Another find thanks to Suyama's extension;

P-1 found a factor in stage #2, B1=85000, B2=[B]1742500[/B].
M2294807 has a factor: 4743377217925125644071

k= 3^3*5*751*3851*[B]2647063[/B]

---

You're welcome drh! I'm learning too, heck we all are.

I usually use [URL]http://factordb.com/[/URL], that site stores the factor as well.

But all the other suggestions are great too.

Mr. P-1 2011-01-17 18:25

[QUOTE=lorgix;246956]Another find thanks to Suyama's extension;[/QUOTE]

E?

lorgix 2011-01-17 18:31

Actually the output doesn't say.

But it always uses E=6 under similar (to the ones in question) circumstances.

drh 2011-01-17 19:44

From TF -

M80307593 has a factor: 144625571114343550097

Mr. P-1 2011-01-17 23:51

[QUOTE=lorgix;247036]Actually the output doesn't say.

But it always uses E=6 under similar (to the ones in question) circumstances.[/QUOTE]

That's curious. Normally it give the E value in the result.txt file, if it's higher than 2.

How many relative primes out of how many were you able to do per pass?

lorgix 2011-01-18 08:07

All 480 in one pass. 498MB.

I used to think the same. But it appears to me now that it doesn't do that if a factor is found.

More recent find below, where Suyama's extension wasn't needed. Still used E=6, but doesn't show it here for some reason.

P-1 found a factor in stage #2, B1=90000, B2=1755000.
M2299571 has a factor: 103653914718894079697

lorgix 2011-01-18 08:12

Close or what?

P-1 found a factor in stage #2, B1=95000, B2=[B]1947500[/B].
M2444359 has a factor: 1588994437060952149274017

k= 2^4*3*31*41*197*13901*[B]1945487[/B]


All times are UTC. The time now is 20:26.

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.