
Re: New integer multiplication algorithm
Posted:
Mar 3, 2005 7:35 AM


In article <2dCQd.37623$g4.710392@news2.nokia.com>, rlankine@hotmail.com says... > > Hi! > > The article below describes a novel way to multiply integers using > a special string notation and a new multiplicationlike operator. > Both are described in the article (informally, but with examples). > > In a nutshell, the notation is used to encode a pair of integers into a > string, whereas the operator is used to "multiply" two soencoded > strings to produce an integer value. The trick is that "squaring" a > string representing a pair of integers effectively multiplies the integers; > hence a suitably tailored square root algorithm might possibly reverse > the multiplication, effectively factoring the source value. > > I'm now publishing my findings to 1) entertain the recreational math > people, and 2) hoping to get some new ideas to either find a faster > factorization method, or to prove the complexity of factorization. > > Enjoy! > >  Risto  > >
Risto,
Just an observation  what would your reaction be if you finally found a way to generate the string from the number (with a method that allowed simple quick processing of very large numbers)?
If I understand correctly a fair proportion of the encryption techniques currently used (and believed to be uncrackable in a "useful" time period) rely on the difficulty and timeconsumption of factorising very large numbers.
You would therefore be in possession of an algorithm that could do one of two things for you personally: 1. Fame and prestige by publication  we are talking front page of Nature and Time etc 2. Great wealth by selling (secretly) to the highest bidder.
These are mutually exclusive  as soon as the world knows that large numbers can be factorised easily (even if the method is not published) those that need real security will stop using them to encrypt and thus nobody would pay that highly for your algorithm.
So, do you provide for yourself, your family etc to live in luxury and ease and damn your prinicples or do you publish?
Regards
Matthew Newell
who would probably give the NSA a single year licence and live on the proceeds, pray noone else discovered in that year and then publish.
> (Please view using fixedwidth font!!!) > >    > > 1. Definition of Notation {s} : > > {s} is a string of digits 0..3 that encodes two odd integers: > > Example: x = 5, y = 11 > > MIN(x,y) 1 0 1 = 5 > ABS(xy)/2 0 1 1 = (115)/2 = 3 > > 10,01,11 > (5,11) = {213} > > Example: x = 11, y = 25 > > MIN(x,y) 1 0 1 1 = 11 > ABS(xy)/2 0 1 1 1 = (2511)/2 = 7 > > 10,01,11,11 > (11,25) = {2133} > > Example: x = 3, y = 135 > > MIN(x,y) 0 0 0 0 0 1 1 = 3 > ABS(xy)/2 1 0 0 0 0 1 0 = (1353)/2 = 66 > > 01,00,00,00,00,11,10 > (3,135) = {1000032} > > > > 2. Definition of Operator # : > > {x} # {y} = nearest_integer( x*y/3 ) > > "#Multiplication" table: > > # {0} {1} {2} {3} > {0} 0 0 0 0 > {1} 0 0 1 1 > {2} 0 1 1 2 > {3} 0 1 2 3 > > Commutativity and associativity apply as if in regular > multiplication of _binary_ numbers: > > {ab} # {xy} = 2 * {a}#{xy} + {b}#{xy} > = 4*{a}#{x} + 2*{a}#{y} + 2*{b}#{x} + {b}#{y} > > Example: > {13} # {32} = 2 * {1}#{32} + {3}#{32} > = 4*{1}#{3} + 2*{1}#{2} + 2*{3}#{3} + {3}#{2} > = 4*1 + 2*1 + 2*3 + 2 = 14 > > > > 3. A new way to multiply: > > Take string (x,y) = {s} ; then {s}#{s} = x*y > > > > 4. A new way to factorize?!? > > Inversely, given n=x*y (but we don't know 'x' or 'y', just 'n') > there is some {s} such that {s}#{s} = n . It may be possible to > adapt some integersquareroot algorithm to find {s} . > > Nevertheless, when {s} has been found, (x,y) are trivial to find, > and they will solve n = x*y . > > Mapping [1] is trivial. Mapping [2] with regular multiplication > is nearly trivial. The challenge is to find an integer square > root algorithm that produces {s}strings. > > > >

