View Single Post
Old 2020-09-15, 17:10   #4
Romulan Interpreter
LaurV's Avatar
Jun 2011

217018 Posts

The algorithm is not "random". You can use some math tricks, and you can get lucky when you select the starting parameters, but the calculus is deterministic.

For example, if you want to factor 2047 and randomly start with 3, you will need 88 iterations to get the loop, but if you randomly start with 622 (which is square root of 1 mod 2047, but you don't know that when you try to factor a big number), you will find after the first iteration 622^2=1 mod 2047, so the gcd(2047, 622-1)=23 and gcd(2047, 622+1)=89 will give you the two factors.

(Welcome to the forum, here you have to make a habit not to reply immediately to posts, give yourself, and us, 10 or 20 minutes, we use to edit our posts because we say a lot of stupid things, and realize after, or make typos, or add examples, like in the post above , moreover, if you spent 15 minutes thinking about the subject, you will find many interesting things, and eventually spot mistakes in our posts too, hehe; then, quoting the immediately preceding post also makes not much sense, people know what is about, unless you quote a particular idea that you reply to, or combat; this has the advantage (for me, hehe) that you don't quote my aberrations before I have time to edit them )

Last fiddled with by LaurV on 2020-09-15 at 17:21
LaurV is offline   Reply With Quote