|
|
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 multiplication-like 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 so-encoded
> 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 time-consumption 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 no-one else discovered in that
year and then publish.
> (Please view using fixed-width 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(x-y)/2 0 1 1 = (11-5)/2 = 3
>
> 10,01,11 -> (5,11) = {213}
>
> Example: x = 11, y = 25
>
> MIN(x,y) 1 0 1 1 = 11
> ABS(x-y)/2 0 1 1 1 = (25-11)/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(x-y)/2 1 0 0 0 0 1 0 = (135-3)/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 integer-square-root 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.
>
>
>
>
|
|
