mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Number Theory Discussion Group (https://www.mersenneforum.org/forumdisplay.php?f=132)
-   -   Repeating residues in LL tests of composite Mersenne numbers (https://www.mersenneforum.org/showthread.php?t=25772)

Dr Sardonicus 2020-12-08 14:45

[QUOTE=LaurV;565631]I had to read that few times and didn't fully got it yet. Why do you need to find both? Only j would be enough. Yet, you still may not factor n after that (you can run in a trivial factor 1 or n).[/QUOTE]I was merely trying to answer the question that had been asked.

In at least one case, things were so blindingly obvious it took me some time to see the answer. File this under [b][color=red]D'oh![/color][/b]

If N = 2^1277 - 1 (a composite M[sub]p[/sub]), then, as we know, N is a base-2 Fermat pseudoprime. But there is no need to factor N-1. It is trivial that the multiplicative order Mod(2, 2^1276 - 1) is 1276, and that therefore (with "a" any base to which

a[sup]N-1[/sup] == 1 (mod N), we have

a^(2^1277) == a^2 (mod N).

And you are absolutely right, this is of little to no help in factoring N. :tu:


All times are UTC. The time now is 16:16.

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