- Jun 30, 2004Kevin Acres writes:

I've been working through the ramifications of my new algorithm and

it seems that it can be used as an encryption busting tool.

First, I'm not sure where the archives of the old list are, but you

might search them for mentions of my so-called "reverse method",

which, I believe, duplicates your new algorithm.

If anyone's still not seeing how it works, perhaps this will help. The

basic idea is simply to add an odd prime, in binary, to itself, shifted

each time so that the prime's units bit (always 1, since the prime is

odd) is under the 0 bit closest to the units bit of the sum-so-far.

Eventually, this will "force" the sum to be all 1's, which, of course,

is a Mersenne number. The smallest "realistic" example is 23, which is

10111 in binary (16 + 4 + 2 + 1):

0

+ 10111

= 10111

+ 10111

= 11001111

+ 10111

= 1000111111

+ 10111

11111111111

Since there are no 0's to the right of any 1 in this sum, we're done.

Note that the final sum has eleven 1's; therefore, 23 divides 2^11 - 1.

Note also that almost all primes lead to a string of 1's with a

composite length; a rather large fraction end up with a string of 1's

with a length of one less than the prime (e.g., 5's string of ones has

length 4).

My newest program that uses this method doesn't do it nearly this

directly; e.g., it factors the decremented input number and uses those

factors to predict the length (rather than calculating it using

addition and shifting as demonstrated above), which turns out to be

much faster (at least for larger input numbers).

As for your thought about your "new algorithm" being used to break

encryption schemes or assist with factoring, I don't think I've seen or

heard those particular ideas anywhere before and they are certainly

interesting. I'd have to try some larger examples to get a better idea

of how helpful it is, however, which I won't have time to do for a few

weeks or more due to other commitments.

Hopefully I won't get the NSA knocking at my door because of this.

Well, they'd likely have knocked on my door years ago, so I think we're

safe.:) Here's the relevant parts of the RCS logs for my most recent

and my first "reverse method" programs. To give you a sense of how

long ago the first one was written, in 1989 I would have been running

it on DEC Vax11/750's (minicomputers, about 0.8MHz(?) CPUs, about

$750,000 retail (educational?) originally in 1981 or so) and DEC

MicroVax II's; MSWindows either didn't exist or wasn't at the Univ. of

Denver, though we did have some IBM AT's running MSDOS with an early MS

Flight Simulator.

Will

http://www.garlic.com/~wedgingt/mersenne.html

RCS file: RCS/1strs8.c,v

Working file: 1strs8.c

head: 7.2

branch:

locks: strict

access list:

symbolic names:

keyword substitution: kv

total revisions: 59; selected revisions: 59

description:

Copy of 1strs6.c v1.86, about to be modified for larger

values (> 2^32) as factors.

----------------------------

revision 7.2

date: 2003/12/28 20:09:11; author: wedgingt; state: Exp; lines: +4 -4

Portability improvements noticed while compiling on Cygwin.

----------------------------

[...]

----------------------------

revision 1.2

date: 1999/02/08 00:48:39; author: wedgingt; state: Exp; lines: +184 -52

First pass at changes to allow arbitrarily large factors. Exponents

still limited to 2^64 - 1 (perhaps less), but that should be

sufficient for decades, expecially for composite exponents, which

are probably going to be < 2^15 for years.

----------------------------

revision 1.1

date: 1999/02/07 01:39:38; author: wedgingt; state: Exp;

Initial revision

=============================================================================

RCS file: RCS/1strs.c,v

Working file: 1strs.c

head: 1.3

branch:

locks: strict

access list:

symbolic names:

keyword substitution: kv

total revisions: 3; selected revisions: 3

description:

Build the ones strings of primes given on stdin.

See comment at top for usage and output format.

----------------------------

revision 1.3

date: 1996/05/16 06:30:53; author: wedgingt; state: Exp; lines: +1 -1

Change to RCS Id.

----------------------------

revision 1.2

date: 1989/03/14 18:42:01; author: wedgingt; state: Exp; lines: +2 -2

Bug fix; was printing 'p' always.

----------------------------

revision 1.1

date: 1989/03/14 18:35:37; author: wedgingt; state: Exp;

Initial revision

============================================================================= - << Previous post in topic