Integer factorization, etc.
in [Math]
|
From: Risto Lankinen on 10 Apr 2008 08:19 On 10 huhti, 14:47, Pubkeybreaker <pubkeybrea...(a)aol.com> wrote: > > What I said was not an ad hominem attack. It was a simple statement of > fact: You do not know enough mathematics to do what you are trying to > do. What, sir, is your impression of what I'm trying to do? Respectfully, - Risto -
From: Pubkeybreaker on 10 Apr 2008 09:18 On Apr 10, 8:19 am, Risto Lankinen <rlank...(a)gmail.com> wrote: > On 10 huhti, 14:47, Pubkeybreaker <pubkeybrea...(a)aol.com> wrote: > > > > > What I said was not an ad hominem attack. It was a simple statement of > > fact: You do not know enough mathematics to do what you are trying to > > do. > > 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.
From: Christian Siebert on 10 Apr 2008 11:16 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? 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). 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)? And maybe a last question (because it's you): 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? Thanks in advance, Christian
From: Pubkeybreaker on 10 Apr 2008 11:56 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. > 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) > > 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. > 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.
From: Risto Lankinen on 10 Apr 2008 17:51
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. Anyway, how new/alternative compared to Fermat's method one has to be in order to be acknowledged as different? Note that I'm not asking judgment as _better_, but as _different_. And laymanship is barely an argument if you consider that Pierre de Fermat was a lawyer, not a mathematician, by education. - - - 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] - - - Note that the beans in cups are equivalent to the numbers of ones in [square] multiplication matrix (please use fixed font!): | 11101 | /11101 | //11101 | ///00000 | ////11101 | ///////// \ | 123232201 4 The top-right to bottom-left diagonals are the cup contents, whilst the top-left to bottom-right diagonal are the odd beans. The sum of the beans is 16, equal to the number of odd beans squared. The following shows why a cup must have two beans for every pair of equidistant odd beans: | #1#01 | /11101 | //#1#01 | ///00000 | ////11101 | ///////// \ | 123232201 4 ^ Two beans here (plus the optional odd bean). - - - Pubkeybreaker refuses (or fails) to understand the point, but does anyone else see any potential in this? - Risto - |