Integer factorization, etc.
in [Math]
|
From: Risto Lankinen on 7 Apr 2008 11:22 On 7 huhti, 18:02, "Dik T. Winter" <Dik.Win...(a)cwi.nl> wrote: > > But the 'k' was integer I thought? Yes indeed, inaccurate of me. My intention was... > Fermat's factorization suffers a fixation to _naturals_, > it's the 'k' in 'N+ki' you really should be interested > about. - Risto -
From: Nick Wedd on 7 Apr 2008 13:00 In message <39d01add-637a-4193-9f87-51c27ba7db9b(a)u69g2000hse.googlegroups.com>, Pubkeybreaker <pubkeybreaker(a)aol.com> writes >On Apr 7, 8:44�am, Risto Lankinen <rlank...(a)gmail.com> wrote: >> On 4 huhti, 17:37, "Dik T. Winter" <Dik.Win...(a)cwi.nl> wrote: >> >> >> >> > But in the Fermat factorisation also the 'non-interesting' cases are >> > interesting. �Consider 91 = 100 - 9, which would factorise 91. �In >> > general, if we have N + d^2 = n^2, and N is odd, then at least one of >> > d or n is even. >> >> Fermat's factorization suffers a fixation to integers, > >Huh? This last sentence is pure gibberish. I think what he means is "Fermat's factorisation method can only be used to factorise natural numbers". He is interested in factorising Gaussian integers. Nick -- Nick Wedd nick(a)maproom.co.uk
From: Pubkeybreaker on 7 Apr 2008 13:37 On Apr 7, 1:00 pm, Nick Wedd <n...(a)maproom.co.uk> wrote: > In message > <39d01add-637a-4193-9f87-51c27ba7d...(a)u69g2000hse.googlegroups.com>, > Pubkeybreaker <pubkeybrea...(a)aol.com> writes > > >On Apr 7, 8:44 am, Risto Lankinen <rlank...(a)gmail.com> wrote: > >> On 4 huhti, 17:37, "Dik T. Winter" <Dik.Win...(a)cwi.nl> wrote: > > >> > But in the Fermat factorisation also the 'non-interesting' cases are > >> > interesting. Consider 91 = 100 - 9, which would factorise 91. In > >> > general, if we have N + d^2 = n^2, and N is odd, then at least one of > >> > d or n is even. > > >> Fermat's factorization suffers a fixation to integers, > > >Huh? This last sentence is pure gibberish. > > I think what he means is "Fermat's factorisation method can only be used > to factorise natural numbers". He is interested in factorising Gaussian > integers. One factors primes that are 1 mod 4 over the Gaussians via Cornachia's algorithm. It runs in polynomial time. 2 factors trivially. Primes that are 3 mod 4 are inert. One factors all other Gaussian numbers by factoring their norms over Z. Hopefully, this ends the discussion.
From: Pubkeybreaker on 7 Apr 2008 13:41 On Apr 7, 10:54 am, Risto Lankinen <rlank...(a)gmail.com> wrote: > On 7 huhti, 16:32, Pubkeybreaker <pubkeybrea...(a)aol.com> wrote: > > > Do not post code. Noone has the time or inclination to read it. > > My article was posted on multiple fora. Please indicate > the particular one that was offended by my article and I'll > discontinue posting there. Stop cross posting. Code is not relevant to any of the groups you posted to. Discussion of algorithms IS relevant. Your article was NOT offensive. But I strongly doubt if anyone will be bothered to read it. The discussion of ALGORITHMS is however relevant in sci.crypt, sci.math, alt.math, alt.math.undergrad etc. And I gave a complete algorithm for how to factor Gaussians in another post.
From: Risto Lankinen on 7 Apr 2008 17:27
On 7 huhti, 20:00, Nick Wedd <n...(a)maproom.co.uk> wrote: > > I think what he means is "Fermat's factorisation method can only be used > to factorise natural numbers". He is interested in factorising Gaussian > integers. Nope. I'm using gaussian integers to factor natural numbers. In the Wikipedia article "One-way function" it says about integer factorization: "Consider the function f that takes as input two integers and multiplies them. This function is easy to compute, but inverting this function requires solving the factoring problem (which is believed to be hard)." As far as I can tell, this is equivalent to: "Consider the function f that takes as input a complex number, multiplies it by itself, and discards imaginary part. This function is easy to compute, but inverting this function requires solving the factoring problem (which is believed to be hard)." Inverting a number multiplied by itself is called a square root. I have discovered a new numeric method for taking the square root of a gaussian integer, which is the gist of my claim. However, because it is very fundamental in the way that it works (for instance, it does not need multiplication of numbers greater than 1 which might make it easily convertible into a satisfiability problem), I am wondering whether it could be modified to work reasonably efficiently even if its argument has an unknown imaginary part. On 7 huhti, 16:32, Pubkeybreaker <pubkeybrea...(a)aol.com> wrote: > > If you want to be taken seriously, then post a description of > the method Here's an informal description: Base i-1 has exponents 1,-1+i,-2i,2+2i,-4,4-4i,8i,-8-8i,16, after which the exponent e[k] = 16*e[k-8] . Every subset of these exponents have a sum which addresses one gaussian integer. Every gaussian integer is addressed by one and only one such subset of exponents. Hence, i-1 can be used as a number base for gaussian integers with digits 0 and 1. Any base which uses only digits 0 and 1 has a unique square signature. Due lack of formal math education, I do not know how to define this in a rigorous manner, but kindly accept description thru a few examples: 11 ==> 121 101 ==> 10201 111 ==> 12321 1001 ==> 1002001 1101 ==> 1212201 1110100101 ==> 1232322234240210201 (Normal decimal calculator can compute square patterns as long as there are at most nine 1's in the source string). Some characteristics of the square signature are: - Only even-indexed (begin at 0) positions can have odd value - Digit in index n depends on the _parities_ of even-indexed digits between 0 and 2n, and only on them - Consequently, the parity of digit 2n depends on the parities of even-indexed digits 2n-2..0 and n Square signature is independent of the base (like the decimal calculator suggestion should point out). However, converting a binary numeric representation of a number into the square signature requires the concept of a carry/borrow. Carry and borrow are /digital invariants/ (=DI) of a given base. In base 10, the DI is {-1,+10} which means that subtracting 1 from a digit in position 'n' and adding 10 to the digit in position 'n-1' does not have any effect to the value of the number that it represents. In base 2 the DI is {-1,+2}, in base -2 the DI is {+1,+2} and in base i-1 the DI is {+1,+2,+2}. Hence, the following are equivalent (in base-2): 11001 = 25 (apply {-1,+2} to bit position 3) 10201 = 25 - Square signature! .... or... 1001 = 9 (apply {-1,+2} to bit position 3) 0201 = 9 (apply {-1,+2} to bit position 2) 0121 = 9 - Square signature! .... or... 1010001 = 81 (apply {-1,+2} to bit position 4) 1002001 = 81 - Square signature! .... or... 110001 = 49 (apply {-1,+2} to bit position 4) 102001 = 49 (apply {-1,+2} to bit position 3) 101201 = 49 (apply {-1,+2} to bit position 5) 021201 = 49 (apply {-1,+2} to bit position 2) 021121 = 49 (apply {-1,+2} to bit position 4) 013121 = 49 (apply {-1,+2} to bit position 3) 012321 = 49 - Square signature! Note that in which order (of bit positions) the digital invariants are applied doesn't matter, but some of the orders may cause intermediate negative values to some digits. That's OK as long as the eventual result is a square signature. Now, in base i-1 ... 111000001 = 9+0i (apply {+1,+2,+2} to bit position 8) 123200001 = 9+0i (apply {+1,+2,+2} to bit position 6) 124420001 = 9+0i (apply {-1,-2,-2} to bit position 7) 112220001 = 9+0i (apply {-1,-2,-2} to bit position 7) 100020001 = 9+0i - Square invariant! (SQRT = 10001 = -3+0i - OK!) Again, the order in which digital invariants are applied does not matter. I have no easy way to describe the algorithm, except by using the source code that I already sent. But let me try anyway: 1. Bit[0] should be 1 (odd numbers only) 2. Every bit[2n+1] should be even. If bit[1] is not even, bail out, because it can't be evened without affecting "fractional" bits using DI= {+1,+2,+2}. If any of bit[3...2n+1] is not even, add DI to make them even. 3. Bit[1] is now =0 or =2 . If Bit[1] = 0, parity of Bit[2] must be even; if Bit[1]=2, parity of Bit[2] must odd. Bail out if not true. 4. Bit[2] is now (0 or 1), or (2 or 3). If (2 or 3), parity of Bit[4] must be odd; else parity of Bit[4] must be even. Going on from here, the bit[n] must reflect the sum of the products of parities of bit[0]*bit[2n] + bit[2]*bit[2n-2] + bit[4]*bit[2n-4]. If 'n' is even, bit[n] may itself be odd if bit[n/2] so determined. To go further, please study the code of function Squirt() in my original example. This process goes on as long as there are non-zero bits in the operand, _and_then_some (up to 8, but perhaps overdoing by just 6 bits is enough). This is due to the fractal nature of the space filling curve generated by base i-1 . Note that this algorithm DOES NOT FACTORIZE! It takes square root of a gaussian integer! (To use it for factorization is a different topic but note that bits 2, 6, 10, 14, etc. in the i-1 representation of a complex number are -2i, 8i, -32i, 64i, etc. which are convenient places to branch for unknowns...) That's all for now. Alas, I can lead a camel to oasis but I can not force one to drink. If you're not interested, please don't waste ammo to shoot down something that you think wasn't flying to begin with. For others, thanks for the interest. Cheers! - Risto - |