Integer factorization, etc.
in [Math]
|
From: Phil Carmody on 11 Apr 2008 12:20 Christian Siebert <iBBiS(a)gmx.de> writes: > Thank you, Bob and Phil, for your replies! > > > > > As far as I understand, this method (Pollard's p-1 method?) is based > > > > on Fermat's little theorem, which works for any base b with 1 < b < p > > > > (if p is the unknown prime factor of N, that we want to find). > > > > > Not quite. You don't want to use b=p-1 (i.e. -1 mod p) > > > > Oooooooooooh. So he's smart enough to spot the out by one > > error on one end, but then shoots himself in the foot at the > > other end. > Good catch! Golly gosh ... > > I just asked these questions because I wondered if this modified > version of Phil's description might be simpler: > > Given an odd integer N > Set b = 2 > Set p^e = 2^1 > As long as N and b-1 are coprime repeat > Let b = b^p modulo N > Find next larger prime or prime power p^e Because that could run for a very long time, and doesn't invite a stage 2. You've complicated your sieve as well. > If gcd(b-1, N) equals N then N is prime Well, that's false for a start. Try factoring Phi(n,2). > otherwise this is a factor of N > > > > > 2) I thought, that this method is just depending on the smoothness of > > > > p-1 and not on the choice of b. Can you explain why you apply a random > > > > selection process for b at the beginning (instead of e.g. assigning a > > > > constant value)? > > > > > I don't know either. Any b is fine except as already noted. > > > > No reason to chose any particular value, no reason to avoid > > any particular value (apart from a few). > > > > Let's meet in the middle - chose a random one. > When this doesn't give us any benefit, then why should I waste > entropy? ;-) Entropy is exceptionally cheap. We have more of it than we want, and it's just going to waste. It'll help factoring Phi(n,2) for a start. > > > > How expensive (upper bound for a deterministic algorithm) would it be > > > > to find an integer k so that, for any given number N and a fixed > > > > smoothness bound B, N*k - 1 is B-smooth? > > > > > It is easy to give an average-case estimate. The probability that > > > NK-1 is B-smooth is u^-u with u = log(NK-1)/log(B). You would > > > need to examine u^u values of K on average. > Ok, although that's still quite a lot, it seems to be feasible (I only > need to find a single k). > Unfortunately, this sounds already outside a polytime solution ... :-( > > How about inverting a small number a (i.e. a < B) mod N? I'd guess > this can be done much more efficiently, right (but here I'd need up to > B of them)? As worded, it's still O(1), as it's impossible. Phil -- Dear aunt, let's set so double the killer delete select all. -- Microsoft voice recognition live demonstration
From: quasi on 11 Apr 2008 14:39 On Fri, 11 Apr 2008 08:26:35 -0700 (PDT), Chip Eastham <hardmath(a)gmail.com> wrote: >On Apr 11, 8:23 am, fortune.br...(a)gmail.com wrote: > >> You really should get your Google on and see what I'm talking about, >> and when you do you will also see that Bob (Pubkeybreaker) has a >> record of not suffering fools easily. >> >> It is also very safe to say that he (Pubkeybreaker) has forgotten more >> about the subject you are on than you will ever know. >> >> I recommend you both show some respect and really try hard to see his >> point. > >Am I the only one who feels a curious loss at learning this? > >One of my favorite book authors and one of more coherent >frequent newsgroup contributors turn out to be the same >person. Somehow I feel I now have fewer folk heroes to >look up to... I think you might be confusing two different Silvermans. I suspect the "author" you alluded to is "Joseph H. Silverman" quasi
From: Chip Eastham on 11 Apr 2008 21:40 On Apr 11, 2:39 pm, quasi <qu...(a)null.set> wrote: > On Fri, 11 Apr 2008 08:26:35 -0700 (PDT), Chip Eastham > > > > <hardm...(a)gmail.com> wrote: > >On Apr 11, 8:23 am, fortune.br...(a)gmail.com wrote: > > >> You really should get your Google on and see what I'm talking about, > >> and when you do you will also see that Bob (Pubkeybreaker) has a > >> record of not suffering fools easily. > > >> It is also very safe to say that he (Pubkeybreaker) has forgotten more > >> about the subject you are on than you will ever know. > > >> I recommend you both show some respect and really try hard to see his > >> point. > > >Am I the only one who feels a curious loss at learning this? > > >One of my favorite book authors and one of more coherent > >frequent newsgroup contributors turn out to be the same > >person. Somehow I feel I now have fewer folk heroes to > >look up to... > > I think you might be confusing two different Silvermans. > > I suspect the "author" you alluded to is "Joseph H. Silverman" > > quasi Ah, right you are! Equilibrium restored (for now). --c
From: Tim Smith on 11 Apr 2008 21:49 In article <c0ebbd99-7de9-4ab9-be83-72b38b5b9064(a)c19g2000prf.googlegroups.com>, fortune.bruce(a)gmail.com wrote: > Pubkeybreaker is Robert Silverman, also known as Bob Silverman, the > "Prince of Primes". > > Robert did seminal work with RSA Labs in the study of the math of > public keys and both trying to break them and make them safer/ > stronger. I reckon that may be the reason for his handle, but I'm > guessing. > > Robert Silverman is a true math legend. He has likely published more > important math papers than the amount of years you've been alive. He > has worked for decades and produced at the highest levels of math and > crypto in the trenches of real work and discovery in this world. > > You really should get your Google on and see what I'm talking about, > and when you do you will also see that Bob (Pubkeybreaker) has a > record of not suffering fools easily. > > It is also very safe to say that he (Pubkeybreaker) has forgotten more > about the subject you are on than you will ever know. > > I recommend you both show some respect and really try hard to see his > point. None of the above, though, is inconsistent with being a jerk. -- --Tim Smith
From: Marshall on 12 Apr 2008 02:39
On Apr 11, 6:49 pm, Tim Smith <reply_in_gr...(a)mouse-potato.com> wrote: > > [...] has a record of not suffering fools easily. [....] > > None of the above, though, is inconsistent with being a jerk. Every time I have ever seen the phrase "not suffer fools gladly," it has been an apologist acknowledgment of a respected person's bad behavior. It's a code phrase used to describe high status jerks. Marshall |