- Hi All,

I'am a new entrant into this group and my interests in primes are

confined to factorisation.So here's the mail,I have a similar kind of

programme which does try to do what you said in the mail,but i think any

regular and systematic method to try and factorising a large integer is

bound to fail as it becomes exponentially more difficult as the number of

digits increase.So I figured out that a semi-random approach would be

best,but my programme has some subtle problems which I feel can be worked

out if I knew what were the previous methods in trying to factorise large

integers and how they failed .

So sir could you please tell me what were the previous

methods(even the failed ones) to try and factorise large integers or could

you direct me to a website which may contain this information?

yours sincerely,

G.RAVI KIRAN.

On Mon, 2 Apr 2001, David Litchfield wrote:

> Howdy all,

> Just a quick question.

>

> Given a number that is the result of multiplying two primes together one can

> work out what these two primes are by squarerooting the given number and

> attempting to divide the number by each whole number below the squareroot.

> This will, though laborious, agreed, eventually give the two factors.

>

> Assuming our number is, say, 1268428227 the squareroot is c. 35615 and

> therefore we'd need to try a maximum of 35615 numbers to get the factors

> using division. Obviously we only need to try odd numbers so this could be

> reduced to 17807 attempts.

>

> If this number of attempts could be reduced further to 2374 (6% of the

> original 35615 attempts) would that be a "good result"? If indeed the number

> of attempts needed to get the factors _could_ be reduced to 2374, how does

> that compare with other methods of factoring?

> - --- paulmillscv <paulmillscv@...> wrote:
> Yes, firmware (a combination of algorithms in hardware) is very

If you know that you will be spending all your time doing bignum

> underexplored for practical implementation of algorithms. So it

> remains now to define a unit of work in mathematics/computer

> science. I imagine something like the 16 bit signed multiplication

> is the unit?

multiplies, then you will look at the most optimal bignum

multiplication algorithm at the firmware level. You can do bignum

multiplies in almost constant time, but it all depends on how much

silicon you want to devote to it. If you know that you're unlikely to

go over 512 bits, then you might want a 512*512 multiplier unit for

example. Again, you have choices of whether you want to minimise

latency or not. If you can pipeline large quantities of operations,

then you don't need a low latency. If everything must be serialised,

then you've got to go for a more expensive low latency design.

(Either that or you explicitly work on two or more different problems

in parallel, but that in turn requires some smarts...)

Phil

__________________________________________________

Do You Yahoo!?

Yahoo! Games - play chess, backgammon, pool and more

http://games.yahoo.com/