Why letting non-mathematicians approach factoring is dangerous

Expand Messages
• To cover my back, I include in reverse order the set of links that I followed that lead me to the subject line. See, nothing to do with current shenanigans.
Message 1 of 14 , Mar 7, 2002
• 0 Attachment
To cover my back, I include in reverse order the set of links that I
followed that lead me to the subject line. See, nothing to do with
current shenanigans.

http://www.computer50.org/mark1/firstprog.html
<<<

The first program was written by Tom Kilburn. It was a program to
find the highest proper factor of any number a; this was done
by trying every integer b from a-1 downward until one was found that
divided exactly into a. The necessary divisions were done not
by long division but by repeated subtraction of b (because the "Baby"

The original number used was quite small, but within a few days he
had built up to trying the program on 218; here around 130,000
numbers were tested, which took about 2.1 million instructions and
involved 3� million store accesses. The correct answer was
obtained in a 52 minute run (in detail ..).
>>>

I hope everyone else shares my pain when reading that. :-|

Phil, holding back the screams!

Back-covering:
from http://www.computer50.org/mark1/new.baby.html
from http://www.computer50.org/mark1/mark1intro.html
from http://www.computer50.org/mark1/decimal-binary.html
from http://www2.hursley.ibm.com/decimal/
from comp.arch.arithmetic :
Subject: Re: Convert algothim
Date: Mon, 04 Mar 2002 23:20:30 +0000
From: Mike Cowlishaw <mfc@...>

=====
--

__________________________________________________
Do You Yahoo!?
Try FREE Yahoo! Mail - the world's greatest free email!
http://mail.yahoo.com/
• ... I m sure that the purpose of this first program was to get a program that works, to test the machine and the programming method, not to be an efficient
Message 2 of 14 , Mar 7, 2002
• 0 Attachment
At 02:24 PM 3/7/2002 -0800, Phil Carmody wrote:

> I hope everyone else shares my pain when reading that. :-|

I'm sure that the purpose of this first program was to get a program that
works, to test the machine and the programming method, not to be an
efficient factoring algorithm.

+---------------------------------------------------------+
| Jud McCranie |
| |
| Programming Achieved with Structure, Clarity, And Logic |
+---------------------------------------------------------+
• Phil, I think that I speak for the entire group by saying: You are absuing this broadcast medium. ... From: Phil Carmody To:
Message 3 of 14 , Mar 7, 2002
• 0 Attachment
Phil,

I think that I speak for the entire group by saying:

You are absuing this broadcast medium.

----- Original Message -----
From: "Phil Carmody" <thefatphil@...>
Sent: Thursday, March 07, 2002 2:24 PM
Subject: [PrimeNumbers] Why letting non-mathematicians approach factoring is
dangerous

> To cover my back, I include in reverse order the set of links that I
> followed that lead me to the subject line. See, nothing to do with
> current shenanigans.
>
>
> http://www.computer50.org/mark1/firstprog.html
> <<<
>
> The first program was written by Tom Kilburn. It was a program to
> find the highest proper factor of any number a; this was done
> by trying every integer b from a-1 downward until one was found that
> divided exactly into a. The necessary divisions were done not
> by long division but by repeated subtraction of b (because the "Baby"
> only had a hardware subtractor).
>
> The original number used was quite small, but within a few days he
> had built up to trying the program on 218; here around 130,000
> numbers were tested, which took about 2.1 million instructions and
> involved 3½ million store accesses. The correct answer was
> obtained in a 52 minute run (in detail ..).
> >>>
>
> I hope everyone else shares my pain when reading that. :-|
>
> Phil, holding back the screams!
>
>
> Back-covering:
> from http://www.computer50.org/mark1/new.baby.html
> from http://www.computer50.org/mark1/mark1intro.html
> from http://www.computer50.org/mark1/decimal-binary.html
> from http://www2.hursley.ibm.com/decimal/
> from comp.arch.arithmetic :
> Subject: Re: Convert algothim
> Date: Mon, 04 Mar 2002 23:20:30 +0000
> From: Mike Cowlishaw <mfc@...>
>
>
> =====
> --
> .sig selecter broken, please ignore.
>
> __________________________________________________
> Do You Yahoo!?
> Try FREE Yahoo! Mail - the world's greatest free email!
> http://mail.yahoo.com/
>
>
> Unsubscribe by an email to: primenumbers-unsubscribe@egroups.com
> The Prime Pages : http://www.primepages.org
>
>
>
> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
>
>
• ... Oh indeed. Having a maximum program size of 32 words didn t help much, either. I interpret the exploit as let s just see how far we can take it, with no
Message 4 of 14 , Mar 7, 2002
• 0 Attachment
--- Jud McCranie <jud.mccranie@...> wrote:
> At 02:24 PM 3/7/2002 -0800, Phil Carmody wrote:
>
> > I hope everyone else shares my pain when reading that. :-|
>
> I'm sure that the purpose of this first program was to get a
> program that
> works, to test the machine and the programming method, not to be an
>
> efficient factoring algorithm.

Oh indeed. Having a maximum program size of 32 words didn't help
much, either. I interpret the exploit as "let's just see how far we
can take it, with no regard to cost, just for the fun of it".

The algorithm isn't quite as bizarre as it first sounds. Given the
remarkably limited 7-instruction instruction set, with basically only
a subtract to do maths with, a reduction modulo a large number can be
performed far quicker than a modulo reduction modulo a small number.

The total cost,
#divisors to test * #subtractions/divisor
is roughly the same whether you look from the smallest up, or the
largest down.

It can be considered similar to the area under a normal unit
hyperbola from 0 to 1 verses 1 to infinity. As near as darn it,
they're the same.

However, if you were to approach a modern-day mathematician and
assert that using trial division from N-1 downwards was the way to
go, he'd think you were _nuts_.

I think that maybe a naive Fermat technique could be implemented on
the architecture, but wouldn't want to have to implement it myself!
sqrt(N) can be found in sqrt(N) operations, using 2nd differences.
That's the easy part, probably less than 10 instructions. After that
it's just a case of walking the lattice points, which is trivial,
until you realise you've only got two dozen instructions left! The
real hacker works out how to share code in this situation!

I believe the "largest factor" part was a red herring. I think they
were looking for any split of the number, and it just so happened
that the algorithm they chose always returned the highest factor,
completely analogously to how trial division always returns the
smallest factor. I.e. it was declared the target after they'd shot
their arrow.

It's funny to think that I have 4 times the capacity of that entire
machine (1kbits) just in my registers!

Phil

=====
--

__________________________________________________
Do You Yahoo!?
Try FREE Yahoo! Mail - the world's greatest free email!
http://mail.yahoo.com/
• ... That is of course 2^18. Sorry for any confusion. Phil ===== -- .sig selecter broken, please ignore. __________________________________________________ Do
Message 5 of 14 , Mar 7, 2002
• 0 Attachment
--- Phil Carmody <thefatphil@...> wrote:
> had built up to trying the program on 218; here around 130,000

That is of course 2^18. Sorry for any confusion.

Phil

=====
--

__________________________________________________
Do You Yahoo!?
Try FREE Yahoo! Mail - the world's greatest free email!
http://mail.yahoo.com/
• ... Actually this last link looks very interesting, especially some of the multi-precision packages such as decNumber and NTL. Can anyone offer any opinions of
Message 6 of 14 , Mar 7, 2002
• 0 Attachment
--- In primenumbers@y..., Phil Carmody <thefatphil@y...> wrote:
Actually this last link looks very interesting, especially
some of the multi-precision packages such as decNumber and NTL.
Can anyone offer any opinions of these and how they compare
with say GMP? To be more specific I've been working with David
Einstein for the last few years on an amicable number search
using a c++ program of his, and have been thinking for a while of
attempting to convert it to a form suitable for up to ~25-30 digits
(currently on a pc only seems reliable to 16d). One of the main
ways it gets speed (besides pruning) is using an array of 1/p values
in trial dividing, so this would still need to be possible.
Also an assembly speed up would be nice!

Andrew Walker
• ... And one thing I read there, it had - but not + , so it must have been easier to decrement a counter than to increment it, which could be a technical
Message 7 of 14 , Mar 7, 2002
• 0 Attachment
At 04:33 PM 3/7/2002 -0800, Phil Carmody wrote:

>Oh indeed. Having a maximum program size of 32 words didn't help
>much, either.

And one thing I read there, it had "-" but not "+", so it must have been
easier to decrement a counter than to increment it, which could be a
technical reason why they had it count down until it found a factor.

+---------------------------------------------------------+
| Jud McCranie |
| |
| Programming Achieved with Structure, Clarity, And Logic |
+---------------------------------------------------------+

[Non-text portions of this message have been removed]
• ... Given signed arithmetic (or unsigned arithemetic which indestinguishable from signed), and no hard-coded decrement instruction, it was just as easy to
Message 8 of 14 , Mar 8, 2002
• 0 Attachment
--- Jud McCranie <jud.mccranie@...> wrote:
> At 04:33 PM 3/7/2002 -0800, Phil Carmody wrote:
>
> >Oh indeed. Having a maximum program size of 32 words didn't help
> >much, either.
>
> And one thing I read there, it had "-" but not "+", so it must have
> been
> easier to decrement a counter than to increment it, which could be
> a
> technical reason why they had it count down until it found a
> factor.

Given signed arithmetic (or unsigned arithemetic which
indestinguishable from signed), and no hard-coded decrement
instruction, it was just as easy to increment a counter as to
decrement one. INC is A<-(A-0xffffffff), DEC is A<-(A-1).
The reason they didn't have an add was simply that add is redundant
if you have sub. They were being purists (actually they were just
trying to get away with as little logic as possible, by increasing
the human logic input). When they increased their instruction set to
16 different instructions, they did include add though, as presumably
the purism got too tedious.

Phil

=====
--

__________________________________________________
Do You Yahoo!?
Try FREE Yahoo! Mail - the world's greatest free email!
http://mail.yahoo.com/
• ... Poorly, in general. Basically, BORG-like, the GMP has assimilated almost all techniques used in other libraries. If you re on a PC, then I can recommend
Message 9 of 14 , Mar 8, 2002
• 0 Attachment
--- andrew_j_walker <ajw01@...> wrote:
> --- In primenumbers@y..., Phil Carmody <thefatphil@y...> wrote:
> > Back-covering:
> > from http://www.computer50.org/mark1/new.baby.html
> > from http://www.computer50.org/mark1/mark1intro.html
> > from http://www.computer50.org/mark1/decimal-binary.html
> > from http://www2.hursley.ibm.com/decimal/
>
> Actually this last link looks very interesting, especially
> some of the multi-precision packages such as decNumber and NTL.
> Can anyone offer any opinions of these and how they compare
> with say GMP?

Poorly, in general. Basically, BORG-like, the GMP has assimilated
almost all techniques used in other libraries. If you're on a PC,
then I can recommend Miracl, and LIP has a few functions which simply
aren't available in GMP.

> To be more specific I've been working with David
> Einstein for the last few years on an amicable number search
> using a c++ program of his, and have been thinking for a while of
> attempting to convert it to a form suitable for up to ~25-30 digits
> (currently on a pc only seems reliable to 16d). One of the main
> ways it gets speed (besides pruning) is using an array of 1/p
> values
> in trial dividing, so this would still need to be possible.
> Also an assembly speed up would be nice!

Don't use arbitrary precision!

Use a _fixed_ precision bignum instead. 25-digits is 3 32-bit words.
You can fully unroll a Baratt (sp?) or Montgomery operation on 3-word
values. 4-words is longer, but still fully unrollable.

If you do write a fixed-size library - please post the code here. I'm
sure some people can help contribute to it. I'll do the 'set to zero'
function, if you like :-)

Phil

=====
--

__________________________________________________
Do You Yahoo!?
Try FREE Yahoo! Mail - the world's greatest free email!
http://mail.yahoo.com/
• ... simply ... Do any of these have a fixed precision largenum type? I ve noticed that the NTL package has a quad_float type which is overloaded and offers ~
Message 10 of 14 , Mar 11, 2002
• 0 Attachment
--- In primenumbers@y..., Phil Carmody <thefatphil@y...> wrote:
> --- andrew_j_walker <ajw01@u...> wrote:
> > --- In primenumbers@y..., Phil Carmody <thefatphil@y...> wrote:
> > > Back-covering:
> > > from http://www.computer50.org/mark1/new.baby.html
> > > from http://www.computer50.org/mark1/mark1intro.html
> > > from http://www.computer50.org/mark1/decimal-binary.html
> > > from http://www2.hursley.ibm.com/decimal/
> >
> > Actually this last link looks very interesting, especially
> > some of the multi-precision packages such as decNumber and NTL.
> > Can anyone offer any opinions of these and how they compare
> > with say GMP?
>
> Poorly, in general. Basically, BORG-like, the GMP has assimilated
> almost all techniques used in other libraries. If you're on a PC,
> then I can recommend Miracl, and LIP has a few functions which
simply
> aren't available in GMP.
>
Do any of these have a fixed precision largenum type? I've noticed
that the NTL package has a quad_float type which is overloaded and
offers ~ 106 bits precision according to the site. This is
implemented as two doubles, the sum of which forms the number. It
also has a RR class which is 53 bits by default but can be varied
in the program.

I've had problems however getting NTL to work which someone
might hopefully be able to sort out (using DJGPP under windows).
After unpacking I copied the folder with NTL's header files into
DJGPP\include. Then I compiled all of the .cpp files in src\
into a static library with:
gcc -g -c *.cpp (creates the .o files)
strip *.o
ar rcs libntl.a *.o
(I got this from
http://www.linuxdoc.org/HOWTO/Program-Library-HOWTO/more-examples.html

libntl.a was then copied into djgpp\include and the tests folder in
ntl. I then tried to compile a stripped down version of the test.cpp
program and get the following errors:

C:\ajw\WinNTL-5_2\tests>gcc -o mytest mytest.cpp -L. -lntl
c:/ajw/djgpp/tmp\ccpIkfr0.o(.text+0x3e):mytest.cpp: undefined
reference to `std::ios_base::Init::Init()'
c:/ajw/djgpp/tmp\ccpIkfr0.o(.text+0xfd):mytest.cpp: undefined
reference to `std::ios_base::Init::~Init()'
c:/ajw/djgpp/tmp\ccpIkfr0.o(.eh_frame+0x11):mytest.cpp: undefined
reference to `__gxx_personality_v0'
collect2: ld returned 1 exit status

Any ideas??

Andrew
• ... Curious. I did know about two pair of floats types, but I think that that s about all there is in the way of big libraries. A guy called Tom St Denis
Message 11 of 14 , Mar 12, 2002
• 0 Attachment
--- andrew_j_walker <ajw01@u...> wrote:
> Do any of these have a fixed precision largenum type? I've noticed
> that the NTL package has a quad_float type which is overloaded and
> offers ~ 106 bits precision according to the site. This is
> implemented as two doubles, the sum of which forms the number. It
> also has a RR class which is 53 bits by default but can be varied
> in the program.

Curious. I did know about two 'pair of floats' types, but I think
that that's about all there is in the way of big libraries.

A guy called 'Tom St Denis' has some fixed precision code on his home
page. Search sci.crypt for a reference. If you have to implement your
own, you can do a lot worse than starting with that as a framework.

> I've had problems however getting NTL to work which someone
> might hopefully be able to sort out (using DJGPP under windows).
> After unpacking I copied the folder with NTL's header files into
> DJGPP\include. Then I compiled all of the .cpp files in src\
> into a static library with:
> gcc -g -c *.cpp (creates the .o files)
> strip *.o
> ar rcs libntl.a *.o
> (I got this from
>
http://www.linuxdoc.org/HOWTO/Program-Library-HOWTO/more-examples.html
>
> libntl.a was then copied into djgpp\include and the tests folder in
>
> ntl. I then tried to compile a stripped down version of the
> test.cpp
> program and get the following errors:
>
> C:\ajw\WinNTL-5_2\tests>gcc -o mytest mytest.cpp -L. -lntl
> c:/ajw/djgpp/tmp\ccpIkfr0.o(.text+0x3e):mytest.cpp: undefined
> reference to `std::ios_base::Init::Init()'
> c:/ajw/djgpp/tmp\ccpIkfr0.o(.text+0xfd):mytest.cpp: undefined
> reference to `std::ios_base::Init::~Init()'
> c:/ajw/djgpp/tmp\ccpIkfr0.o(.eh_frame+0x11):mytest.cpp: undefined
> reference to `__gxx_personality_v0'
> collect2: ld returned 1 exit status
>
> Any ideas??

Ooooh, never ask a C++ lecturer a question like that... C and C++ are
different languages that happen to have a large common subset. Apart
rom that they shouldn't be confused with each other.

My guess is that 'gcc' wants to link as if the code's C, but the code
is really C++ abd calls upon standard C++ libraries that aren't
linked by default. I use 'g++' to compile C++ personally.

Phil

=====
--

__________________________________________________
Do You Yahoo!?
Try FREE Yahoo! Mail - the world's greatest free email!
http://mail.yahoo.com/
• ... are ... code ... Thanks for fixing my bout of stupidity! Actually djgpp has gpp as its c++ compiler which makes it more confusing... After this and a few
Message 12 of 14 , Mar 17, 2002
• 0 Attachment
--- In primenumbers@y..., Phil Carmody <thefatphil@y...> wrote:

>
> Ooooh, never ask a C++ lecturer a question like that... C and C++
are
> different languages that happen to have a large common subset. Apart
> rom that they shouldn't be confused with each other.
>
> My guess is that 'gcc' wants to link as if the code's C, but the
code
> is really C++ abd calls upon standard C++ libraries that aren't
> linked by default. I use 'g++' to compile C++ personally.
>

Thanks for fixing my bout of stupidity! Actually djgpp has gpp
as its c++ compiler which makes it more confusing...

After this and a few other changes with the librarys I finally
managed to get the amicable program up and working using NTL's
quadfloat type, the only test so far is that it correctly finds
all pairs of 9 digits or less. Are there any good pages/books
on the best method for rounding of floats/doubles whatever to the
nearest integer? (and remaining the same type).I used floor(num+eps)
where eps is say 10^-4, however I'm sure there must be a better
method. "Numerical Recipes" wasn't any help.

Andrew
• ... Ermm... float myValue = something; int myRoundedFloat = (int)(myValue + .5); That s rounding to the *nearest* integer for -.5
Message 13 of 14 , Mar 17, 2002
• 0 Attachment
andrew_j_walker wrote:
>
> Are there any good pages/books
> on the best method for rounding of floats/doubles whatever to the
> nearest integer?

Ermm...

float myValue = something;
int myRoundedFloat = (int)(myValue + .5);

That's rounding to the *nearest* integer for -.5 <= myValue
<= MAXINT. For positive and negative values of myValue,
use:

int myRoundedFloat = (int)(myValue + ( (myValue < 0.) ? -.5
: .5 ));

This should work in C, C++, or Java. In C or C++ you might
want to use long instead of int. I hope I didn't miss the
entire point of the question.

-- Dan Morenus (dmorenus@...)

-- This parachute is not warranted to be suitable --
-- for any purpose, including descending safely --
-- from an airplane to the ground. --
• To be fair that was the first programme on the first computer! The Maths Dept was responsible for the programming. Six weeks after the birth of Baby someone
Message 14 of 14 , Apr 4, 2002
• 0 Attachment
To be fair that was the first programme on the first computer!
The Maths Dept was responsible for the programming.
Six weeks after the birth of Baby someone called Alan Turing
joined the project to lead the software team, and soon he and
Prof Newman (Fielden Professor of Pure Mathematics at
Manchester Univ) were searching for Mersenne Primes.

http://www.computer50.org/mark1/maths.html#turing
"Before Turing started work in Manchester he asked for the
Baby order code and sent up a routine for long division,"
"As soon as the Manchester Mark 1 was generally available for
use in April 1949, he enthusiastically set about using it, especially
to investigate Mersenne Primes, in collaboration with Newman."
Though they were working towards this usage from "Summer 1948".
Mark 1, notably the random number generator. It is also likely that
he and Newman influenced the comprehensive set of instructions
provided on the Manchester Mark 1 in connection with the double
length accumulator, since they required multi-length arithmetic for
their Mersenne Primes work. (In practice there was little subsequent
usage of the Mark 1s for anything longer than double-length
arithmetic)."
That would be the first example of prime testing and multi-length
calculations on a computer.
Turing and Newman tested prime exponents from 258 to 511 on
Baby, without finding any primes. In the end the next Mersenne
prime was found in 1952, at M521 (by Robinson). This is the very
next prime exponent!!!

I would argue that Kilburn´s Highest Factor Routine was an excellent
test programme. Kilburn would have been interested in testing his
storage device, and this is good engineering. The results were already
known, and any error would have been easily spotted. They had
attempted runs prior to June 21st 1948, but that was the first time it
worked.
In fact the "Kilburn Highest Factor Routine (amended)" of 18th July was
clearly a test programme.
http://www.computer50.org/mark1/firstprog.html
"The original program was encoded in only 17 instructions. The revised
version includes two extra instructions to facilitate rerunning the program
with the same number (in detail ...). This was a sensible thing to do until
the basic reliability of the Baby had been demonstrated."
Kilburn would have known that it was not neccessary to start at A-1, he
could have started at [A/2], but Baby didn't have a divide by 2 order :-)
A macro could have easily been written or they could have inputted
[A/2] and had the programme double and add one to get A.

Whilst most of the funding for Baby was provided by the military
organisation "The Telecommunications Research Establishment",
interestingly Turing was not being paid by Manchester Univ or the TRE.

http://www.computer50.org/mark1/maths.html#turing
"Turing joined the Department of Mathematics as a Reader in September
1948, with the nominal title of "Deputy Director of the Royal Society
Computing Machine Laboratory". (The Royal Society Computing Machine
Laboratory was the room the Baby occupied; there was no known
"Director"!)",
well not with a name anyway.

http://www.computer50.org/mark1/turing.html
Turing started work for the Government Code and Cypher School
(a euphemism for a secret service dept) in August 1938, joining
Bletchley Park working on the Enigma codes full time at the start of the
war, where Newman was also working.
"In November 1942 Turing went to the States for four months, to liaise at
the highest level on the current U-boat crisis and on a proposed scrambling
device they were building to maintain secrecy in conversations between
Churchill and Roosevelt."
Turing was later promoted to a "General Consultancy role". He was the
British Liaison Officer in the US at the time of the formation of the No
Such
Agency.

http://www.turing.org.uk/turing/bio/part6.html says of the Manchester
computing project:-
"He had no control over the project whose fate was in fact determined by
its sudden necessity for the British atomic bomb project."

Turing must have been well paid as he bought his own house in Wilmslow
(posh!).
http://www.turing.org.uk/turing/bio/part7.html
"unknown to most around him was that he had also continued to work for
GCHQ, the post-war successor to Bletchley Park, on the basis of a personal
connection with Alexander, now its director. But since 1948, the conditions
of the Cold War, and the alliance with the United States, meant that known
homosexuals had become ineligible for security clearance."
Back in 1952, security clearance and teenage rent-boys were XORed.
After Turing´s arrest and conviction for Homosexuality and Gross Indecency,
he lost his security clearance and was branded a "major security risk".

He died 7th June 1954 after an apple was dipped into cyanide (not found
in his house) and Alan Turing`s mouth dipped into the apple several times.
That's dangerous.

Cheers,
Paul Landon

=================================================
Phil Carmody wrote:-
To cover my back, I include in reverse order the set of links that I
followed that lead me to the subject line. See, nothing to do with
current shenanigans.

http://www.computer50.org/mark1/firstprog.html
<<<

The first program was written by Tom Kilburn. It was a program to
find the highest proper factor of any number a; this was done
by trying every integer b from a-1 downward until one was found that
divided exactly into a. The necessary divisions were done not
by long division but by repeated subtraction of b (because the "Baby"

The original number used was quite small, but within a few days he
had built up to trying the program on 218; here around 130,000
numbers were tested, which took about 2.1 million instructions and
involved 3½ million store accesses. The correct answer was
obtained in a 52 minute run (in detail ..).
>>>

I hope everyone else shares my pain when reading that. :-|

Phil, holding back the screams!

Back-covering:
from http://www.computer50.org/mark1/new.baby.html
from http://www.computer50.org/mark1/mark1intro.html
from http://www.computer50.org/mark1/decimal-binary.html
from http://www2.hursley.ibm.com/decimal/
from comp.arch.arithmetic :
Subject: Re: Convert algothim
Date: Mon, 04 Mar 2002 23:20:30 +0000
From: Mike Cowlishaw <mfc@u...>

--
GMX - Die Kommunikationsplattform im Internet.
http://www.gmx.net
Your message has been successfully submitted and would be delivered to recipients shortly.