|
|
| Author |
Message |
Risto Lankinen
science forum beginner
Joined: 02 Jun 2005
Posts: 28
|
 Posted: Tue Jun 13, 2006 8:46 am Post subject:
Manuscript for factoring large numbers?
|
|
|
Act 1:
A fast integer square root algorithm exists which works by
finding each next significant bit at a time comparing the most
resent partial result to the argument. I didn't find example
source code for this algorithm in the 'net, but it's reasonably
straightforward to implement. Let an example suffice here:
Argument N = 87 = 1010111b
Candidate X
High bit of X = 16 too large, because X^2 = 128 > 87
High bit of X = 8 alright, because X^8 = 64 <= 87
Next highest bit of X = 8+4 too large because 12^2 > 87
Next highest bit of X = 8+2 too large because 10^2 > 87
Next highest bit of X = 8+1 alright, because 9^2 <=87
Now we're out of [integer] bits, so the result is X=9 and
the remainder is 6. (We could go on ad infinitum to find
fractional binary digits, though, but that's less interesting
when it comes to factorization.)
Note that the argument does not need not be fixed during
the computation, as long as any changes happen "behind
the bit horizon" (e.g. are smaller than each next highest bit
squared).
Act 2:
There is a number base that can express complex numbers
with binary digits. The exponentiating "integer" for this base
is i-1 . Here are the first few of its exponents:
1, -1+i, -2i, 2+2i, -4, 4+4i, 8i, -8-8i, 16, at which point the
series recurs, multiplied by 16.
Any integer-complex can be expressed with 0's and 1's by
summing a certain subset of said series. Arithmetics is also
possible, although the borrow rule is slightly more complex
than in usual binary [in binary, b^n = b^(n-1)+b^(n-1) but
in base i-1 , b^n = b^(n-3)+b^(n-3)-b^(n-1) ]
Note, that (in case someone attempts to convert the square
root algorithm I just explained above for complex integers 
the borrow rule pushes back the "bit horizon" by two bits.
Act 3:
To factor a number N is equivalent to finding the square root
of N+ki, where k is dependent on the factors of N:
(a+di)^2 = (a^2-d^2) + 2adi
.... where N = a^2-d^2 , or (a+d)(a-d), or x*y with x>y, and...
.... where k = 2ad = 2*(x+y)/2*(x-y)/2 = (x^2-y^2)/2 .
Put differently, given N, find k such that N+ki is a perfect square
in integer complex numbers. When the result, a+di , is found, the
factors of N will be (a+d) and (a-d) .
Intermission:
Looks like we could construct an approximate representation of
N+ki using the complex integers. We don't know 'k' but we can
gradually learn its high bits when we compute the "square root"
of N+ki . In fact, we'd be learning them at exactly the correct
pace to resolve each next highest bit in the candidate.
Alas, the #%&* "bit horizon" will not let us know the high bits of
the complex part before it's too late. Or will it?!?
Act 4:
How do we keep the k = 2ad a few magnitudes smaller than
the N = a^2-d^2 during the computation? Clearly 'd' needs to
be minimized, since this effectively increases N and decreases
'k' at the same time. Now, d = (x-y)/2 so minimizing 'd' would
require that the number-to-factor should have its factors as
nearly the same as possible.
Time for a side plot: There's a puzzle where the three sons of
a deceased shejk cannot divide the 17 camels he left behind to
his sons to inherit. His will dictates that the eldest son gets 1/2
of the camels, the middle son gets 1/3 and the youngest son gets
1/9 . They couldn't even get started since 17 doesn't divide by
two to begin with... until a passer-by kindly lends his own camel
which he gets back after the division leaves exactly one camel
as the remainder.
Act 5:
So, why don't we add metaphorical camels to N to see if it
becomes more evenly divisible (referring to the magnitudes
of the factors). If N = x*y , then one of the following...
N=x*y , 2N=x*(2y), 4N=x*(4y), ... , 2^b*N=(2^b*y)*x
.... will have factor ratio x :: 2^b*y within 1 :: SQRT(2) of each
other (note that at some point 2^b*y grows above 'x' exactly
as shown above in the last term). Now the 2ad is pushed back
towards the "bit horizon" by 1.5 bits. Not enough, but we can
do better by adding 3- and 5-camels as well. Perhaps some
combination of 2-, 3-, 5- and maybe 7- camels will guarantee
that the factors of...
2^r*3^s*5^t*N =
(x*2^r_x*3^s_x*5^t_x)*(y*2^r_y*3^s_y*5^t_y)
.... are such that (a^2-d^2) / (2ad) is always greater than 2^3 ,
effectively pushing the k=2ad beyond the "bit horizon" with
respect to the N=a^2-d^2 . Clearly 2^r*3^s*5^t must be
smaller than N/(2^bit_horizon) for otherwise we may end up
with the result N = (xy)*(2^r*3^s*5^t) and will have learned
nothing of the factors 'x' and 'y'. However, it also neatly limits
the combinatorial explosion of how many of which camels to
try out. If any of the resultant camel sets yields a number that
can be efficiently and "nearly deterministically" square-rooted,
then... then... then...
Epilogue:
Day job and two kids means not much time to experiment with
this idea. However, I'd like to challenge the top experts of the
field to either shoot it down, or make it work. Shoot it down
and I'll forever hold my breath (I have absolutely no intention to
start harrising on this forum), but I strongly believe there's much
of potential in it. I wouldn't mind the fame, though, if someone
makes a breakthru based on these ideas.
Cheers!
- Risto - |
|
| Back to top |
|
 |
Pubkeybreaker
science forum Guru
Joined: 24 Mar 2005
Posts: 333
|
| Posted: Tue Jun 13, 2006 11:29 am Post subject:
Re: Manuscript for factoring large numbers?
|
|
|
Risto Lankinen wrote:
Gibberish |
|
| Back to top |
|
|
bert
science forum addict
Joined: 04 Jan 2006
Posts: 54
|
| Posted: Tue Jun 13, 2006 1:26 pm Post subject:
Re: Manuscript for factoring large numbers?
|
|
|
Risto Lankinen wrote:
| Quote: | Act 1:
A fast integer square root algorithm exists which works by
finding each next significant bit at a time comparing the most
resent partial result to the argument. I didn't find example
source code for this algorithm in the 'net, but it's reasonably
straightforward to implement. Let an example suffice here:
Argument N = 87 = 1010111b
Candidate X
High bit of X = 16 too large, because X^2 = 128 > 87
High bit of X = 8 alright, because X^8 = 64 <= 87
Next highest bit of X = 8+4 too large because 12^2 > 87
Next highest bit of X = 8+2 too large because 10^2 > 87
Next highest bit of X = 8+1 alright, because 9^2 <=87
Now we're out of [integer] bits, so the result is X=9 and
the remainder is 6. (We could go on ad infinitum to find
fractional binary digits, though, but that's less interesting
when it comes to factorization.)
Note that the argument does not need not be fixed during
the computation, as long as any changes happen "behind
the bit horizon" (e.g. are smaller than each next highest bit
squared).
Act 2:
There is a number base that can express complex numbers
with binary digits. The exponentiating "integer" for this base
is i-1 . Here are the first few of its exponents:
1, -1+i, -2i, 2+2i, -4, 4+4i, 8i, -8-8i, 16, at which point the
series recurs, multiplied by 16.
Any integer-complex can be expressed with 0's and 1's by
summing a certain subset of said series. Arithmetics is also
possible, although the borrow rule is slightly more complex
than in usual binary [in binary, b^n = b^(n-1)+b^(n-1) but
in base i-1 , b^n = b^(n-3)+b^(n-3)-b^(n-1) ]
Note, that (in case someone attempts to convert the square
root algorithm I just explained above for complex integers
the borrow rule pushes back the "bit horizon" by two bits.
Act 3:
To factor a number N is equivalent to finding the square root
of N+ki, where k is dependent on the factors of N:
(a+di)^2 = (a^2-d^2) + 2adi
... where N = a^2-d^2 , or (a+d)(a-d), or x*y with x>y, and...
... where k = 2ad = 2*(x+y)/2*(x-y)/2 = (x^2-y^2)/2 .
Put differently, given N, find k such that N+ki is a perfect square
in integer complex numbers. When the result, a+di , is found, the
factors of N will be (a+d) and (a-d) .
Intermission:
Looks like we could construct an approximate representation of
N+ki using the complex integers. We don't know 'k' but we can
gradually learn its high bits when we compute the "square root"
of N+ki . In fact, we'd be learning them at exactly the correct
pace to resolve each next highest bit in the candidate.
Alas, the #%&* "bit horizon" will not let us know the high bits of
the complex part before it's too late. Or will it?!?
Act 4:
How do we keep the k = 2ad a few magnitudes smaller than
the N = a^2-d^2 during the computation? Clearly 'd' needs to
be minimized, since this effectively increases N and decreases
'k' at the same time. Now, d = (x-y)/2 so minimizing 'd' would
require that the number-to-factor should have its factors as
nearly the same as possible.
Time for a side plot: There's a puzzle where the three sons of
a deceased shejk cannot divide the 17 camels he left behind to
his sons to inherit. His will dictates that the eldest son gets 1/2
of the camels, the middle son gets 1/3 and the youngest son gets
1/9 . They couldn't even get started since 17 doesn't divide by
two to begin with... until a passer-by kindly lends his own camel
which he gets back after the division leaves exactly one camel
as the remainder.
Act 5:
So, why don't we add metaphorical camels to N to see if it
becomes more evenly divisible (referring to the magnitudes
of the factors). If N = x*y , then one of the following...
N=x*y , 2N=x*(2y), 4N=x*(4y), ... , 2^b*N=(2^b*y)*x
... will have factor ratio x :: 2^b*y within 1 :: SQRT(2) of each
other (note that at some point 2^b*y grows above 'x' exactly
as shown above in the last term). Now the 2ad is pushed back
towards the "bit horizon" by 1.5 bits. Not enough, but we can
do better by adding 3- and 5-camels as well. Perhaps some
combination of 2-, 3-, 5- and maybe 7- camels will guarantee
that the factors of...
2^r*3^s*5^t*N =
(x*2^r_x*3^s_x*5^t_x)*(y*2^r_y*3^s_y*5^t_y)
... are such that (a^2-d^2) / (2ad) is always greater than 2^3 ,
effectively pushing the k=2ad beyond the "bit horizon" with
respect to the N=a^2-d^2 . Clearly 2^r*3^s*5^t must be
smaller than N/(2^bit_horizon) for otherwise we may end up
with the result N = (xy)*(2^r*3^s*5^t) and will have learned
nothing of the factors 'x' and 'y'. However, it also neatly limits
the combinatorial explosion of how many of which camels to
try out. If any of the resultant camel sets yields a number that
can be efficiently and "nearly deterministically" square-rooted,
then... then... then...
Epilogue:
Day job and two kids means not much time to experiment with
this idea. However, I'd like to challenge the top experts of the
field to either shoot it down, or make it work. Shoot it down
and I'll forever hold my breath (I have absolutely no intention to
start harrising on this forum), but I strongly believe there's much
of potential in it. I wouldn't mind the fame, though, if someone
makes a breakthru based on these ideas.
Cheers!
- Risto -
|
I don't think your approach via complex integers gives
anything extra compared to Fermat/Lehman factorisation
with a simple multiplier k, k * N = P^2 - Q^2, where for
some suitable (or lucky) choice of k, Q is small. When
N is a product of two primes greater than N^(1/3), there
is some value of k less than about N^(1/3) such that
P^2 - k * N is a perfect square for the very first
choice of P, namely ceil(sqrt(k * N)). With smaller
values of k, there are various tricks to search more
quickly for the P which gives a perfect Q^2, but they
still don't make this a competitive method, and yours
seems to have no better prospects.
-- |
|
| Back to top |
|
|
Amicus
science forum Guru Wannabe
Joined: 29 Jun 2005
Posts: 100
|
| Posted: Fri Jun 16, 2006 5:03 am Post subject:
Re: Manuscript for factoring large numbers?
|
|
|
Risto Lankinen said:
| Quote: | Time for a side plot: There's a puzzle where the three sons of
a deceased shejk cannot divide the 17 camels he left behind to
his sons to inherit. His will dictates that the eldest son gets 1/2
of the camels, the middle son gets 1/3 and the youngest son gets
1/9 . They couldn't even get started since 17 doesn't divide by
two to begin with... until a passer-by kindly lends his own camel
which he gets back after the division leaves exactly one camel
as the remainder.
|
But the eldest son, who is supposed to get 8.5 camels, gets 9.
The second son is supposed to get 5.66+ camels, but gets 6.
The youngest son, who is supposed to get almost 1.89 camels, gets 2.
In total, this represents an overpayment of 0.94+ camels to the family,
which means the lawyer's fee goes unpaid, and he successfully sues the
family, getting /all/ the camels as compensation.
The "camel trick" is fun for puzzlers, but should not be used in "real"
mathematics.
--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously) |
|
| Back to top |
|
|
Douglas A. Gwyn
science forum beginner
Joined: 13 May 2005
Posts: 26
|
| Posted: Fri Jun 16, 2006 7:17 pm Post subject:
Re: Manuscript for factoring large numbers?
|
|
|
Richard Heathfield wrote:
| Quote: | Risto Lankinen said:
Time for a side plot: There's a puzzle where the three sons of
a deceased shejk cannot divide the 17 camels he left behind to
his sons to inherit. His will dictates that the eldest son gets 1/2
of the camels, the middle son gets 1/3 and the youngest son gets
1/9 . They couldn't even get started since 17 doesn't divide by
two to begin with... until a passer-by kindly lends his own camel
which he gets back after the division leaves exactly one camel
as the remainder.
But the eldest son, who is supposed to get 8.5 camels, gets 9.
The second son is supposed to get 5.66+ camels, but gets 6.
The youngest son, who is supposed to get almost 1.89 camels, gets 2.
In total, this represents an overpayment of 0.94+ camels to the family,
which means the lawyer's fee goes unpaid, and he successfully sues the
family, getting /all/ the camels as compensation.
The "camel trick" is fun for puzzlers, but should not be used in "real"
mathematics.
|
I don't think the puzzle was a proper one to start with.
1/2 + 1/3 + 1/9 = 17/18 where the logic requires 1.
There is a somewhat similar puzzle involving monkeys and
coconuts that can be easily solved by adding artificial
"blue coconuts" which are all that remain at the end of
the allocation process.. That's in one of the old
Mathematical Games books; I don't remember which one. |
|
| Back to top |
|
|
Amicus
science forum Guru Wannabe
Joined: 29 Jun 2005
Posts: 100
|
| Posted: Fri Jun 16, 2006 8:34 pm Post subject:
Re: Manuscript for factoring large numbers?
|
|
|
[This is nothing to do with crypto or numerical analysis any more, if it
ever was, so followups are set to rec.puzzles]
Douglas A. Gwyn said:
| Quote: | Richard Heathfield wrote:
Risto Lankinen said:
Time for a side plot: There's a puzzle where the three sons of
a deceased shejk cannot divide the 17 camels he left behind to
his sons to inherit. His will dictates that the eldest son gets 1/2
of the camels, the middle son gets 1/3 and the youngest son gets
1/9 . They couldn't even get started since 17 doesn't divide by
two to begin with... until a passer-by kindly lends his own camel
which he gets back after the division leaves exactly one camel
as the remainder.
But the eldest son, who is supposed to get 8.5 camels, gets 9.
The second son is supposed to get 5.66+ camels, but gets 6.
The youngest son, who is supposed to get almost 1.89 camels, gets 2.
In total, this represents an overpayment of 0.94+ camels to the family,
which means the lawyer's fee goes unpaid, and he successfully sues the
family, getting /all/ the camels as compensation.
The "camel trick" is fun for puzzlers, but should not be used in "real"
mathematics.
I don't think the puzzle was a proper one to start with.
1/2 + 1/3 + 1/9 = 17/18 where the logic requires 1.
|
Hence my suggestion, above, that the other 1/18th was supposed to go to the
lawyer.
| Quote: | There is a somewhat similar puzzle involving monkeys and
coconuts that can be easily solved by adding artificial
"blue coconuts" which are all that remain at the end of
the allocation process.. That's in one of the old
Mathematical Games books; I don't remember which one.
|
"On a desert island, five men and a monkey gather coconuts all day, then
sleep. The first man awakens, and decides to take his share. He divides the
coconuts into five equal shares, with one coconut left over. He gives the
extra one to the monkey, hides his share, and goes to sleep. Later, the
second man awakens, and takes his fifth from the remaining pile; he too
finds one extra and gives it to the monkey. Each of the remaining three men
does likewise in turn. Find the minimum number of coconuts originally
present."
I think you'll find it recounted in either "Mathematical Recreations and
Diversions" or "More Mathematical Recreations and Diversions", each by
Martin Gardner, but I may even have those titles wrong because I can find
neither book right now.
--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously) |
|
| Back to top |
|
|
Mark Brader
science forum beginner
Joined: 25 May 2005
Posts: 15
|
| Posted: Sat Jun 17, 2006 12:34 am Post subject:
Re: Manuscript for factoring large numbers?
|
|
|
Risto Lankinen:
| Quote: | Time for a side plot: There's a puzzle where the three sons of
a deceased shejk cannot divide the 17 camels he left behind to
his sons to inherit. His will dictates that the eldest son gets 1/2
of the camels, the middle son gets 1/3 and the youngest son gets
1/9 ...
|
Doug Gwyn:
| Quote: | I don't think the puzzle was a proper one to start with.
1/2 + 1/3 + 1/9 = 17/18 where the logic requires 1.
|
As I must have mentioned in rec.puzzles before, I've come across a
variant that takes care of that objection. In the variant, the will
dictates that the camels are left in *proportions* of 1/2, 1/3, and
1/9 to the three sons. Of course the reader is supposed to assume
that the use of "proportions" is just legal verbiage and not notice
that it makes 1/2:1/3:1/9 into a ratio. Which also means that the
"borrow a camel" solution then actually produces the right result.
--
Mark Brader, Toronto | "If you feel [that Doug Gwyn] has a bad attitude,
msb@vex.net | then use lint (or Chris Torek...)" --Joe English
My text in this article is in the public domain. |
|
| Back to top |
|
|
James Dow Allen
science forum beginner
Joined: 20 Sep 2005
Posts: 9
|
| Posted: Sun Jun 18, 2006 7:36 am Post subject:
Re: Manuscript for factoring large numbers?
|
|
|
Mark Brader wrote:
| Quote: | Doug Gwyn:
I don't think the puzzle was a proper one to start with.
1/2 + 1/3 + 1/9 = 17/18 where the logic requires 1.
As I must have mentioned in rec.puzzles before, I've come across a
variant that takes care of that objection.
|
IMHO, it's borrowing the camel and later returning it,
whether strictly "legal" or not, that changes this from
a trivial bit of arithmetic to a cute and inventive classic.
James |
|
| Back to top |
|
|
George Weinberg
science forum beginner
Joined: 25 May 2005
Posts: 11
|
| Posted: Sun Jun 18, 2006 5:16 pm Post subject:
Re: Manuscript for factoring large numbers?
|
|
|
On 18 Jun 2006 00:36:01 -0700, "James Dow Allen"
<jdallen2000@yahoo.com> wrote:
| Quote: |
Mark Brader wrote:
Doug Gwyn:
I don't think the puzzle was a proper one to start with.
1/2 + 1/3 + 1/9 = 17/18 where the logic requires 1.
As I must have mentioned in rec.puzzles before, I've come across a
variant that takes care of that objection.
IMHO, it's borrowing the camel and later returning it,
whether strictly "legal" or not, that changes this from
a trivial bit of arithmetic to a cute and inventive classic.
James
|
But of course you don't have to have a camel to "borrow".
The trick is that the hearer isn't supposed to notice that the
fractions don't add up to one because he is distracted by
the "problem" that you can't give out fractional camels.
As a famous lunatic pointed out, if a camel is a dime,
that doesn't mean half a camel is a nickle.
ObPuzzle: which lunatic?
George |
|
| Back to top |
|
|
gerson
science forum beginner
Joined: 27 Jun 2006
Posts: 1
|
| Posted: Tue Jun 27, 2006 9:55 am Post subject:
Re: Manuscript for factoring large numbers?
|
|
|
"George Weinberg" On 18 Jun 2006 wrote:
| Quote: | As a famous lunatic pointed out, if a camel is a dime,
that doesn't mean half a camel is a nickle.
ObPuzzle: which lunatic?
|
Frank knicklemacher ? |
|
| Back to top |
|
|
George Weinberg
science forum beginner
Joined: 25 May 2005
Posts: 11
|
| Posted: Tue Jun 27, 2006 4:54 pm Post subject:
Re: Manuscript for factoring large numbers?
|
|
|
On Tue, 27 Jun 2006 09:56:57 GMT, "gerson" <gerson@bigpond.net.au>
wrote:
| Quote: |
"George Weinberg" On 18 Jun 2006 wrote:
As a famous lunatic pointed out, if a camel is a dime,
that doesn't mean half a camel is a nickle.
ObPuzzle: which lunatic?
Frank knicklemacher ?
|
McMurphy in "One Flew Over the Cukoo's Nest". The nuts are
playing poker with cigarettes (could have been camels) representing
dimes, one tries to bet half a cigarette as a nickle.
George |
|
| Back to top |
|
|
Google
|
|
| Back to top |
|
|
|
|
The time now is Sat Jan 10, 2009 1:03 am | All times are GMT
|
|
Home Loan | Singapore Shopping Guide | Loans | Credit Card Menu | Free Advertising
|
|
Copyright © 2004-2005 DeniX Solutions SRL
|
|
Other DeniX Solutions sites:
Electronics forum |
Medicine forum |
Unix/Linux blog |
Unix/Linux documentation |
Unix/Linux forums
|
Powered by phpBB © 2001, 2005 phpBB Group
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
Forum index
»
Science and Technology
»
Math
»
num-analysis
