Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.


Math Forum » Discussions » sci.math.* » sci.math

Topic: New integer multiplication algorithm
Replies: 26   Last Post: Mar 10, 2005 3:26 PM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Matthew Newell

Posts: 3
Registered: 12/13/04
Re: New integer multiplication algorithm
Posted: Mar 3, 2005 7:35 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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.
>
>
>
>



Date Subject Author
2/16/05
Read New integer multiplication algorithm
Risto Lankinen
2/16/05
Read Re: New integer multiplication algorithm
Oscar Lanzi III
2/16/05
Read Re: New integer multiplication algorithm
fiziwig
2/16/05
Read Re: New integer multiplication algorithm
Oscar Lanzi III
2/17/05
Read Re: New integer multiplication algorithm
Proginoskes
2/17/05
Read Re: New integer multiplication algorithm
Oscar Lanzi III
3/3/05
Read Re: New integer multiplication algorithm
Matthew Newell
3/3/05
Read Re: New integer multiplication algorithm
Risto Lankinen
3/3/05
Read Re: New integer multiplication algorithm
Daniel A. Jimenez
3/3/05
Read Re: New integer multiplication algorithm
Dave Rusin
3/3/05
Read Re: New integer multiplication algorithm
Mike Robson
3/3/05
Read Re: New integer multiplication algorithm
Phil Carmody
3/4/05
Read Re: New integer multiplication algorithm
Matthew Russotto
3/4/05
Read Re: New integer multiplication algorithm
Proginoskes
3/4/05
Read Re: New integer multiplication algorithm
Willem
3/8/05
Read Re: New integer multiplication algorithm
Proginoskes
3/9/05
Read Re: New integer multiplication algorithm
Willem
3/9/05
Read Re: New integer multiplication algorithm
Glenn C. Rhoads
3/9/05
Read Re: New integer multiplication algorithm
Willem
3/9/05
Read Re: New integer multiplication algorithm
Glenn C. Rhoads
3/9/05
Read Re: New integer multiplication algorithm
Willem
3/10/05
Read Re: New integer multiplication algorithm
Proginoskes
3/4/05
Read Re: New integer multiplication algorithm
Frank J. Lhota
3/8/05
Read Re: New integer multiplication algorithm
Matthew Russotto
3/3/05
Read Re: New integer multiplication algorithm
Proginoskes
3/4/05
Read Re: New integer multiplication algorithm
Matthew Newell
3/3/05
Read Re: New integer multiplication algorithm
oberon

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.