Integer factorization, etc.
in [Math]
|
From: quasi on 10 Apr 2008 19:27 On Thu, 10 Apr 2008 14:51:40 -0700 (PDT), Risto Lankinen <rlankine(a)gmail.com> wrote: >Let me change my approach a little bit. I'll present >a puzzle: > > - SQUARE WHEEL - > >Square wheel is played on a sufficient number of cups >and beans. Cups are arranged in a row with a starting >point and an arbitrarily large ending point. Cups are >labeled with numbers 0..n . Cups with an even label >are black, and odd label are white. At the beginning, >each cup can be empty, or have one bean in it. > >Definition: >Odd bean is any one bean in a cup that has an odd >number of beans. > >Rules: >1. White cups shall not contain odd beans. >2a. Every cup shall contain two beans for every pair >of distinct equidistant odd beans, counting both left >and right from the cup itself. >2b. Black cups are additionally allowed to contain an >odd bean. >3a. A move consists of adding two beans to any cup, >and adding two beans to the cup indexed one higher, >and adding one bean to the cup indexed two higher. >3b. A move may be reversed by corresponding removals >of beans. > >Goal: >Satisfy constraints [1] and [2] by applying moves [3] >repeatedly, or deem the task impossible. > >Observations: > >If the goal is reached the total number of beans will >be a square number. Every move adds 5 beans; hence a >starting number of beans equal to 2 or 3 MOD 5 can be >immediately deemed impossible. > >If the goal is reached, the number of odd beans will >be equal to the square root of the total number of >beans. > >Additional rule: >4. You may optionally add 1, 2, or 3 beans to any cup >having index 4n+2. [The connection to base i-1 has >not been made yet, but if it were, this rule would >be equivalent to adding 0..3 * 2i / -8i / 32i / -128i >etc. imaginary units to the operand] I haven't had time to look at it closely, but on first glance, it does seem interesting. Whether it leads to anything new and important, who knows? But don't let that deter you. As long as the quest provides insights, and is fun, so what if you end up reinventing a wheel, and moreover, possibly a square wheel. At the same time, it doesn't hurt to self-educate by doing some study of the existing knowledge base. However, in my opinion, the continued study of the ideas of others should not be at the expense of deferring all of your own ideas, naive though they may be. Otherwise, those ideas might be deferred forever. In any case, it seems like you are off to an inspired start. Let the spirit of Fermat be with you! quasi
From: Phil Carmody on 10 Apr 2008 18:52 Pubkeybreaker <pubkeybreaker(a)aol.com> writes: > On Apr 10, 11:16�am, Christian Siebert <iB...(a)gmx.de> wrote: > > Hi Phil, > > > > please let me ask two questions regarding your description: > > > > > So the description of a simple P-1-like factoring > > > algorithm would be: > > > > > Given integer N > > > Select a suitable bound B > > > Take a random integer 2<b<N-1 > > > For each prime p<B > > > � Let b = b^(p^i) modulo N where i is maximal and p^i<=B > > > If gcd(b-1, N) is 1, repeat with a higher bound > > > Else if it's N, then repeat with a lower bound > > > Otherwise, it's a factor of N > > > > 1) Why do you exclude 2 as a starting value for b? > > I suspect a simple typo. (i.e. < vs <=) b=2 is fine as well. Thanks for fielding that, Bob - all googlegroups posters (apart from 6 select individuals) are now in my killfile. You're bang on. Typo. So easily spotted it demonstrates that the level of detail I suggested was just about right for discussion of the algorithm. Which of course was my point. So thanks to Christian for demonstating that the pseudocode spat out in a fraction of a second was in fact understandable enough to be immediately analysable. My point is made. > > 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. Can I bring marshmallows? > > 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. No reason to avoid it, right? > > 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. The only fully proven > upper > bound would be much worse than this, AFAIK if you are looking for a > guaranteed solution. I think the answer to the question asked is O(1), assuming you're permitted to apply enough pedantry. However, I've just had 15 different beers from 5 different countries, and may well be hilariously wrong. You are invited to laugh at my expense. Then buy me a beer :-) Phil -- Dear aunt, let's set so double the killer delete select all. -- Microsoft voice recognition live demonstration
From: fortune.bruce on 11 Apr 2008 08:23 On Apr 10, 2:51 pm, Risto Lankinen <rlank...(a)gmail.com> wrote: > On 10 huhti, 16:18, Pubkeybreaker <pubkeybrea...(a)aol.com> wrote: > > > On Apr 10, 8:19 am, Risto Lankinen <rlank...(a)gmail.com> wrote: > > > > What, sir, is your impression of what I'm trying to do? > > > It was given in your first post in this thread: You are trying > > to present a new/alternative method of implementing Fermat's method > > although you didn't even know of the existence of Fermat's method, > > what is is, or how it works. > > > It is a clear instance of trying to run before you can walk. > > Won't argue. Could, but just won't. > <snip argument you said you wouldn't make but did> > > Pubkeybreaker refuses (or fails) to understand > the point, but does anyone else see any potential > in this? > > - Risto - I know... logic should be allowed to prevail without whipping out the titles and accomplishments, but when it doesn't,,, Do you know who you are arguing (poorly) with? Have any idea? 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. Bruce
From: Christian Siebert on 11 Apr 2008 11:19 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 If gcd(b-1, N) equals N then N is prime 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? ;-) > > > 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)? Best regards, Christian
From: Chip Eastham on 11 Apr 2008 11:26
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... regards, chip |