mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Data (https://www.mersenneforum.org/forumdisplay.php?f=21)
-   -   Mersenne number factored (disbelievers are biting elbows) (https://www.mersenneforum.org/showthread.php?t=19407)

petrw1 2020-12-17 17:02

As I get older I notice 2 things starting to happen:

1. I repeat myself
2. I repeat myself

xilman 2020-12-17 17:40

[QUOTE=Dr Sardonicus;566442]"It's not nice to make people spray coffee all over their monitors."[/QUOTE]Aka C|N>K


Or have you forgotten that too?

Dr Sardonicus 2020-12-17 21:25

[QUOTE=xilman;566457]Aka C|N>K


Or have you forgotten that too?[/QUOTE]
I have never seen that before. Therefore I have not forgotten it.

Maciej Kmieciak 2020-12-20 18:15

The 350th fully-factored or probably-fully-factored Mersenne number with prime exponent
 
The 350th fully-factored or probably-fully-factored Mersenne number with prime exponent (not including the Mersenne primes themselves) is [URL="https://www.mersenne.org/M1399"]M1399[/URL].

The most recent factor (61 digits) was found by Ryan Propper on December 19 (UTC) and the PRP test was done by mikr and myself. There are 3 factors in all, plus the cofactor.

Dr Sardonicus 2020-12-20 19:48

[QUOTE=Maciej Kmieciak;566781]The 350th fully-factored or probably-fully-factored Mersenne number with prime exponent (not including the Mersenne primes themselves) is [URL="https://www.mersenne.org/M1399"]M1399[/URL].

The most recent factor (61 digits) was found by Ryan Propper on December 19 (UTC) and the PRP test was done by mikr and myself. There are 3 factors in all, plus the cofactor.[/QUOTE]FWIW, I ran Pari-GP's isprime() on this PRP308 with the following result:

[code]? n=(2^1399-1)/28875361/4320651071020341609502042221583629017824960697/9729831901051958663829453004687723271026191923786080297556081;

? isprime(n)

%2 = 1[/code]

It didn't take very long.

The manual entry says[quote]3.4.31 isprime(x, {flag = 0}): true (1) if x is a (proven) prime number, false (0) otherwise. This can be very slow when x is indeed prime and has more than 1000 digits, say. Use ispseudoprime to quickly check for pseudo primality. See also factor.

If flag = 0, use a combination of Baillie-PSW pseudo primality test (see ispseudoprime), Selfridge "p − 1" test if x − 1 is smooth enough, and Adleman-Pomerance-Rumely-Cohen-Lenstra (APRCL) for general x.[/quote]

paulunderwood 2021-02-24 06:42

@James,

[URL="https://primes.utm.edu/primes/page.php?id=132049"]M82939 cofactor[/URL] is certified prime

Jean Penné 2021-02-24 09:16

Congrats for this nice result!
 
[QUOTE=paulunderwood;572397]@James,

[URL="https://primes.utm.edu/primes/page.php?id=132049"]M82939 cofactor[/URL] is certified prime[/QUOTE]

Many congrats, Paul!

Jean

P.S. : How did you do the PRP test before the certification using Primo ?

paulunderwood 2021-02-24 09:46

Thanks, Jean.

I merely got the candidate from [url]www.mersenne.ca[/url]. I might have run a 3-PRP to be sure-ish. Anyway, Primo does a quick Fermat+Lucas à la BPSW before embarking on a lengthy ECPP path.

Jean Penné 2021-02-24 09:51

[QUOTE=paulunderwood;572410]Thanks, Jean.

I merely got the candidate from [url]www.mersenne.ca[/url]. I might have run a 3-PRP to be sure-ish. Anyway, Primo does a quick Fermat+Lucas à la BPSW before embarking on a lengthy ECPP path.[/QUOTE]

Thank you for this detail!

Jean

James Heinrich 2021-02-24 14:46

[QUOTE=paulunderwood;572397][URL="https://primes.utm.edu/primes/page.php?id=132049"]M82939 cofactor[/URL] is certified prime[/QUOTE]I have updated [url=https://www.mersenne.ca/prp.php?show=2&min_exponent=82000&max_exponent=83000#M82939]my PRP list[/url], thanks.

R. Gerbicz 2021-02-24 20:17

[QUOTE=Jean Penné;572405]
P.S. : How did you do the PRP test before the certification using Primo ?[/QUOTE]

[QUOTE=paulunderwood;572410]Thanks, Jean.

I merely got the candidate from [url]www.mersenne.ca[/url]. I might have run a 3-PRP to be sure-ish. Anyway, Primo does a quick Fermat+Lucas à la BPSW before embarking on a lengthy ECPP path.[/QUOTE]

We had already a Prp-cf test on this:
[url]https://www.mersenne.org/report_exponent/?exp_lo=82939&exp_hi=&full=1[/url]

Notice that for N=(k*2^n+c)/d we're using a Fermat test using
base^d as base, then
(base^d)^N=base^d mod N should hold for a prp number. So

base^(k*2^n+c)==base^d mod N, to help a lot we're using reduction mod (d*N)=mod (k*2^n+c).
Then do only one big division at the end of the test, in real life d is "small", at most ~1000 bits. And you can build in a strong check in the routine like for the normal prp test for k*2^n+c numbers. There is only a very small slow down at error check, because here our base is "large".

ps. so actually p95 has done a Fermat test using 3^d as base, and not 3. The reason is that we have a check only for 3^d [or base^d].


All times are UTC. The time now is 22:54.

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