mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math > Number Theory Discussion Group

Reply
 
Thread Tools
Old 2020-12-08, 14:45   #23
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

5,009 Posts
Default

Quote:
Originally Posted by LaurV View Post
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).
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 D'oh!

If N = 2^1277 - 1 (a composite Mp), 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

aN-1 == 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.
Dr Sardonicus is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Factoring composite Mersenne numbers using Pollard Rho jshort Factoring 9 2019-04-09 16:34
question: decidability for quadratic residues modulo a composite LaurV Math 18 2017-09-16 14:47
2 holes in bizarre theorem about composite Mersenne Numbers wildrabbitt Math 120 2016-09-29 21:52
Use Pepin's Tests for proving primality of Mersenne numbers ? T.Rex Math 12 2016-04-03 22:27
Factoring highly composite Mersenne numbers philmoore Factoring 21 2004-11-18 20:00

All times are UTC. The time now is 12:25.


Wed Oct 27 12:25:40 UTC 2021 up 96 days, 6:54, 0 users, load averages: 1.62, 1.93, 1.83

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

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.