Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #5677 > unrolled thread

really? (lame question about primes)

Back to article view | Back to comp.programming

Contents

  really? (lame question about primes) fir <profesor.fir@gmail.com> - 2015-08-31 12:07 -0700
    Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-08-31 23:23 +0100
      Re: really? (lame question about primes) fir <profesor.fir@gmail.com> - 2015-09-01 01:18 -0700
        Re: really? (lame question about primes) David Brown <david.brown@hesbynett.no> - 2015-09-01 11:01 +0200
          Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-09-01 12:20 +0100
            Re: really? (lame question about primes) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-09-01 15:48 +0100
              Re: really? (lame question about primes) fir <profesor.fir@gmail.com> - 2015-09-01 13:26 -0700
                Re: really? (lame question about primes) Robert Wessel <robertwessel2@yahoo.com> - 2015-09-02 02:12 -0500
                  Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-09-02 08:38 +0100
                    Re: really? (lame question about primes) David Brown <david.brown@hesbynett.no> - 2015-09-02 14:03 +0200
            Re: really? (lame question about primes) fir <profesor.fir@gmail.com> - 2015-09-01 13:24 -0700
              Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-09-01 22:27 +0100
                Re: really? (lame question about primes) fir <profesor.fir@gmail.com> - 2015-09-01 15:02 -0700
                  Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-09-01 23:20 +0100
                    Re: really? (lame question about primes) bartekltg <bartek@gmail.com> - 2015-09-02 01:22 +0200
                      Re: really? (lame question about primes) fir <profesor.fir@gmail.com> - 2015-09-01 17:18 -0700
                        Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-09-02 02:19 +0100
                          Re: really? (lame question about primes) James Dow Allen <gmail@jamesdowallen.nospam> - 2015-09-02 12:42 +0000
                            Re: really? (lame question about primes) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-09-02 14:21 +0100
                              Re: really? (lame question about primes) Johannes Bauer <dfnsonfsduifb@gmx.de> - 2015-09-02 17:45 +0200
                                Re: really? (lame question about primes) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-09-02 18:06 +0100
                                  Re: really? (lame question about primes) James Dow Allen <jdallen2000@yahoo.com> - 2015-09-03 17:05 -0700
                                    Re: really? (lame question about primes) bartekltg <bartek@gmail.com> - 2015-09-04 02:18 +0200
                                      Re: really? (lame question about primes) Chad <cdalten@gmail.com> - 2015-09-03 22:37 -0700
                                        Re: really? (lame question about primes) fir <profesor.fir@gmail.com> - 2015-09-03 23:49 -0700
                                          Re: really? (lame question about primes) fir <profesor.fir@gmail.com> - 2015-09-04 00:18 -0700
                                        Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-09-04 08:25 +0100
                            Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-09-02 14:36 +0100
                              Re: really? (lame question about primes) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-09-02 16:49 +0100
                                Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-09-02 17:32 +0100
              Re: really? (lame question about primes) Kaz Kylheku <kaz@kylheku.com> - 2015-09-01 22:55 +0000
                Re: really? (lame question about primes) bartekltg <bartek@gmail.com> - 2015-09-02 01:15 +0200
            Re: really? (lame question about primes) bartekltg <bartek@gmail.com> - 2015-09-02 03:19 +0200
              Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-09-02 02:37 +0100
                Re: really? (lame question about primes) bartekltg <bartek@gmail.com> - 2015-09-02 11:24 +0200
                  Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-09-02 10:42 +0100
                    Re: really? (lame question about primes) fir <profesor.fir@gmail.com> - 2015-09-02 03:01 -0700
                    Re: really? (lame question about primes) bartekltg <bartek@gmail.com> - 2015-09-02 12:28 +0200
                    Re: really? (lame question about primes) David Brown <david.brown@hesbynett.no> - 2015-09-02 14:12 +0200
                      Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-09-02 13:19 +0100
                        Re: really? (lame question about primes) bartekltg <bartek@gmail.com> - 2015-09-02 14:56 +0200
                          Re: really? (lame question about primes) David Brown <david.brown@hesbynett.no> - 2015-09-02 15:47 +0200
                            Re: really? (lame question about primes) bartekltg <bartek@gmail.com> - 2015-09-02 16:27 +0200
                              Re: really? (lame question about primes) David Brown <david.brown@hesbynett.no> - 2015-09-02 16:37 +0200
                                Re: really? (lame question about primes) bartekltg <bartek@gmail.com> - 2015-09-02 17:01 +0200
                                  Re: really? (lame question about primes) David Brown <david.brown@hesbynett.no> - 2015-09-03 10:55 +0200
                                    Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-09-03 10:05 +0100
                                      Re: really? (lame question about primes) David Brown <david.brown@hesbynett.no> - 2015-09-03 11:49 +0200
                                        Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-09-03 10:54 +0100
                                          Re: really? (lame question about primes) David Brown <david.brown@hesbynett.no> - 2015-09-03 13:22 +0200
                                    Re: really? (lame question about primes) bartekltg <bartek@gmail.com> - 2015-09-03 13:58 +0200
                      Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-09-02 13:34 +0100
    Re: really? (lame question about primes) Robert Wessel <robertwessel2@yahoo.com> - 2015-08-31 23:10 -0500

Page 2 of 3 — ← Prev page 1 [2] 3  Next page →

#5727

Johannes Bauer <dfnsonfsduifb@gmx.de> writes:

> On 02.09.2015 15:21, Ben Bacarisse wrote:
>
>>> (Please tell us how you did it.)
>> 
>> Too embarrassed!
>
> sage:
> print(factor(6666666666666666666666666666666664295863450544367679162527001239842359
> ))
> 67499999992406250000094921874999003 * 98765432109876543210987654321098453
>
> Took just over 2 minutes on my system. Was that how you did it?

I used gp (PARI).  I think sage uses gp in places so it may be exactly
the same.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#5793

On Thursday, September 3, 2015 at 12:06:49 AM UTC+7, Ben Bacarisse wrote:
> I used gp (PARI).  I think sage uses gp in places so it may be exactly
> the same.
> 
> -- 
> Ben.

The task seems to be too hard for cygwin's factor(1).
Any easy guide to downloading the better source with
all needed headers and libraries?

James

[toc] | [prev] | [next] | [standalone]

#5794

On 04.09.2015 02:05, James Dow Allen wrote:
> On Thursday, September 3, 2015 at 12:06:49 AM UTC+7, Ben Bacarisse wrote:
>> I used gp (PARI).  I think sage uses gp in places so it may be exactly
>> the same.
>>
>> --
>> Ben.
>
> The task seems to be too hard for cygwin's factor(1).
> Any easy guide to downloading the better source with
> all needed headers and libraries?

PARI is a C library (used by a 'calculator' GP)
http://pari.math.u-bordeaux.fr/download.html

You can link it with gmp, it will be faster,
but it is not necessary.
http://pari.math.u-bordeaux.fr/benchs/timings-int.html

Library documentation:
http://pari.math.u-bordeaux.fr/pub/pari/manuals/2.7.0/libpari.pdf

bartekltg

[toc] | [prev] | [next] | [standalone]

#5795

I was reading this thread and noticed fir was insulting people. This is kind of not amusing since not too long ago this idiot was complaining he/she/it was an unsuccessful programmer. 

[toc] | [prev] | [next] | [standalone]

#5796

W dniu piątek, 4 września 2015 07:37:53 UTC+2 użytkownik Chad napisał:
> I was reading this thread and noticed fir was insulting people. This is kind of not amusing since not too long ago this idiot was complaining he/she/it was an unsuccessful programmer.

we have small explosion of primitives-cheaters here, you fit them very nicely poormind primitive, lets see if they will accept you in their team of poorminds: joined by common stupidity - i see you urge to ba accepted in the group 
but judging your mind level you will be stupidest one even in donkey team

[toc] | [prev] | [next] | [standalone]

#5797

W dniu piątek, 4 września 2015 08:49:41 UTC+2 użytkownik fir napisał:
> W dniu piątek, 4 września 2015 07:37:53 UTC+2 użytkownik Chad napisał:
> > I was reading this thread and noticed fir was insulting people. This is kind of not amusing since not too long ago this idiot was complaining he/she/it was an unsuccessful programmer.
> 
> we have small explosion of primitives-cheaters here, you fit them very nicely poormind primitive, lets see if they will accept you in their team of poorminds: joined by common stupidity - i see you urge to ba accepted in the group 
> but judging your mind level you will be stupidest one even in donkey team

which i may ad to you - as i often do - is your imaginary team, you imagine that other people are so stupid as you (this is known in psychology of primitives, "stupidity projection" it goes all the time here) thus imagining your own audience of stupids - where you really are quite alone - as it is somewhat seen (at least i see this)

[toc] | [prev] | [next] | [standalone]

#5798

On 04/09/2015 06:37, Chad wrote:
> I was reading this thread and noticed fir was insulting people. This is kind of not amusing since not too long ago this idiot was complaining he/she/it was an unsuccessful programmer.

Anyone who tries to help fir is eventually labelled as a "primitive 
commonist insulter", and even perhaps a "babler", so there is no 
particular reason why anyone should help him unless they enjoy being 
insulted.

Sturgeon's Law applies. He's been posting for several months now, and I 
think he's been right twice, possibly three times, in all that time. His 
articles do not merit close attention. Just move on to the next article.

-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

[toc] | [prev] | [next] | [standalone]

#5719

On 02/09/2015 13:42, James Dow Allen wrote:
> Richard Heathfield<rjh@cpax.org.uk>  might have writ, in news:d8sFx.324164
> $tz.265438@fx02.am4:
>
>>  Here's a product of two primes:
>>
>>  58240024563391777851261291575917006595873586378340\
>>  06933501482037788347032155265963843106235363953614\
>>  49841148805852200248028532053742301130515851591046\
>>  09780764992214765245952615895162196506824080887010\
>>  84909798795532569027855897144990861217719976822376\
>>  60245183108382607111271438893289345453397044868767\
>>  74937653432105197140786655752847106640293149009133\
>>  49133637852917819933171853595092059610555346845194\
>>  20546782513079321228879093216436059864014065839170\
>>  63336369425428124884924467183572745778186732426767\
>>  31177226131629502125332694404335922836373000524949\
>>  96264733742856842752930777926209786527196791359153\
>>  71
>>
>>  Good luck factoring it.
>
> Now you're just being sadistic.  (And BTW how did you come up with that
> number?)

Pick a number of bits (I chose a thousand, I think).
Round it up to a whole number of octets.
Set the top bit (to make it big).
Set the bottom bit (to make it odd).
Clear or set the rest of the bits at "random" (using a ghastly entropy 
generator that I am too embarrassed to divulge).
While trial division by small primes fails or, failing that, 
Miller-Rabin (20 tests) fails:
   Add 2
Endwhile
Do that all again.
Multiply the two numbers together.
Post the product on Usenet.
We're done here.

> I'll be impressed by whoever is first to factor this number
> 6666666666666666666666666666666664295863450544367679162527001239842359
> (Please tell us how you did it.)

Ben posted his answer before I'd even read the question! It's a shame 
that his embarrassment prevents him from revealing his method, but 
perhaps it's for the best - if he explained, we would say (just as 
Watson said after Holmes had explained a deduction) "Oh, how absurdly 
simple!" So let's just applaud Ben and spare him his blushes.

-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

[toc] | [prev] | [next] | [standalone]

#5725

Richard Heathfield <rjh@cpax.org.uk> writes:

> On 02/09/2015 13:42, James Dow Allen wrote:
<snip>
>> I'll be impressed by whoever is first to factor this number
>> 6666666666666666666666666666666664295863450544367679162527001239842359
>> (Please tell us how you did it.)
>
> Ben posted his answer before I'd even read the question! It's a shame
> that his embarrassment prevents him from revealing his method, but
> perhaps it's for the best - if he explained, we would say (just as
> Watson said after Holmes had explained a deduction) "Oh, how absurdly
> simple!" So let's just applaud Ben and spare him his blushes.

It's embarrassing only because I did nothing interesting.  I ran 'gp'
and typed

 factor(6666666666666666666666666666666664295863450544367679162527001239842359)

at the prompt just to see if it could, and after minute or two it
replied:

  %1 = 
  [67499999992406250000094921874999003 1]
  [98765432109876543210987654321098453 1]

(the 1s because it shows a list of primes and powers).  It would be so
much better if I could have talked about elliptic curves and number
field sieves so as to appear wise.  Oh look, I just did!

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#5726

On 02/09/2015 16:49, Ben Bacarisse wrote:
> Richard Heathfield<rjh@cpax.org.uk>  writes:
>
<snip>
>>  perhaps it's for the best - if he explained, we would say (just as
>>  Watson said after Holmes had explained a deduction) "Oh, how absurdly
>>  simple!" So let's just applaud Ben and spare him his blushes.
>
> It's embarrassing only because I did nothing interesting.  I ran 'gp'
> and typed
>
>   factor(6666666666666666666666666666666664295863450544367679162527001239842359)
>
> at the prompt just to see if it could, and after minute or two it
> replied:
>
>    %1 =
>    [67499999992406250000094921874999003 1]
>    [98765432109876543210987654321098453 1]

Oh, how absurdly simple!

-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

[toc] | [prev] | [next] | [standalone]

#5695

On 2015-09-01, fir <profesor.fir@gmail.com> wrote:
> W dniu wtorek, 1 września 2015 13:20:29 UTC+2 użytkownik Richard Heathfield napisał:
>> There are only 9*10^299 300-digit numbers, so we need to test 81*10^598 
>> = 8.1*10^599 pairs.
>> 
> preposterous bullshit - i said that A length is strictly related to B length 

You can demonstrate your superior intellect by winning some prime factorization
contest, like this one:

https://en.wikipedia.org/wiki/RSA_Factoring_Challenge#The_prizes_and_records

Plus you can earn tens of thousands of dollars.

[toc] | [prev] | [next] | [standalone]

#5696

On 02.09.2015 00:55, Kaz Kylheku wrote:
> On 2015-09-01, fir <profesor.fir@gmail.com> wrote:
>> W dniu wtorek, 1 września 2015 13:20:29 UTC+2 użytkownik Richard Heathfield napisał:
>>> There are only 9*10^299 300-digit numbers, so we need to test 81*10^598
>>> = 8.1*10^599 pairs.
>>>
>> preposterous bullshit - i said that A length is strictly related to B length
>
> You can demonstrate your superior intellect by winning some prime factorization
> contest, like this one:
>
> https://en.wikipedia.org/wiki/RSA_Factoring_Challenge#The_prizes_and_records
>
> Plus you can earn tens of thousands of dollars.


Too late.

"The RSA challenges ended in 2007.[1] RSA Laboratories stated: "Now
that the industry has a considerably more advanced understanding of the
cryptanalytic strength of common symmetric-key and public-key
algorithms, these challenges are no longer active."[2]"

bartekltg

[toc] | [prev] | [next] | [standalone]

#5700

On 01.09.2015 13:20, Richard Heathfield wrote:
> On 01/09/2015 10:01, David Brown wrote:
>
> <snip>
>
>> Yes, you can factorise C by trying to multiply pairs A * B and see if
>> they match.  The trouble is, with a 600 digit number there are quite a
>> lot of such pairs to try!
>
> Well, there aren't all that many really, and the OP specified two
> 300-digit integers, so we needn't bother with lower numbers.
>
> There are only 9*10^299 300-digit numbers, so we need to test 81*10^598
> = 8.1*10^599 pairs.


We do not need to check every _pair_, it is enough to
test if C%A == 0 for any A, so "only" 9*10^299 iterations.

Still it is too much for a computer... or whole universe.

bartekltg

[toc] | [prev] | [next] | [standalone]

#5701

On 02/09/2015 02:19, bartekltg wrote:
> On 01.09.2015 13:20, Richard Heathfield wrote:
>>  On 01/09/2015 10:01, David Brown wrote:
>>
>>  <snip>
>>
>>>  Yes, you can factorise C by trying to multiply pairs A * B and see if
>>>  they match.  The trouble is, with a 600 digit number there are quite a
>>>  lot of such pairs to try!
>>
>>  Well, there aren't all that many really, and the OP specified two
>>  300-digit integers, so we needn't bother with lower numbers.
>>
>>  There are only 9*10^299 300-digit numbers, so we need to test 81*10^598
>>  = 8.1*10^599 pairs.
>
>
> We do not need to check every _pair_, it is enough to
> test if C%A == 0 for any A, so "only" 9*10^299 iterations.

But division is a lot more expensive than multiplication (i.e. it takes 
longer to perform the tests).

Let me give you some hard data:

Earlier, I posted the product of two primes. The multiplication took 
0.018 seconds. On the same computer, dividing the product by one of the 
primes took 0.04 seconds - a little over twice as long.

So you don't actually save anything by doing C%A instead of A*B. (Also, 
if I could be bothered, I could make the multiplication faster by using 
Anatolii Karatsuba's algorithm instead of just mimicking the 
paper-and-pencil method as I do now. But I don't know of any way to make 
the division faster than I already have it.)

> Still it is too much for a computer... or whole universe.

But we won't let that stop us, will we? :-)

-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

[toc] | [prev] | [next] | [standalone]

#5707

On 02.09.2015 03:37, Richard Heathfield wrote:
> On 02/09/2015 02:19, bartekltg wrote:
>> On 01.09.2015 13:20, Richard Heathfield wrote:
>>>  On 01/09/2015 10:01, David Brown wrote:
>>>
>>>  <snip>
>>>
>>>>  Yes, you can factorise C by trying to multiply pairs A * B and see if
>>>>  they match.  The trouble is, with a 600 digit number there are quite a
>>>>  lot of such pairs to try!
>>>
>>>  Well, there aren't all that many really, and the OP specified two
>>>  300-digit integers, so we needn't bother with lower numbers.
>>>
>>>  There are only 9*10^299 300-digit numbers, so we need to test 81*10^598
>>>  = 8.1*10^599 pairs.
>>
>>
>> We do not need to check every _pair_, it is enough to
>> test if C%A == 0 for any A, so "only" 9*10^299 iterations.
>
> But division is a lot more expensive than multiplication (i.e. it takes
> longer to perform the tests).

...than multiplication by 10^299 numbers?
No, it is not!

Seriously, are you trolling?


> Let me give you some hard data:
>
> Earlier, I posted the product of two primes. The multiplication took
> 0.018 seconds. On the same computer, dividing the product by one of the
> primes took 0.04 seconds - a little over twice as long.

If I use iterative, methods, division will be ~log_2(number of bits)
longer than multiplication.
This isn't the best method. Still, for 300 lets say it is 1000
times longer.

So you can use divison, it is "1000 times longer",
or check for every pair of primes, that is 10^299 times longer.


> So you don't actually save anything by doing C%A instead of A*B. (Also,

You seriously claim that 10^299 divisions is the same as
10^598 (every pair) multiplication? Yes, you are trolling.

bartekltg

[toc] | [prev] | [next] | [standalone]

#5708

On 02/09/2015 10:24, bartekltg wrote:
> On 02.09.2015 03:37, Richard Heathfield wrote:
>>  On 02/09/2015 02:19, bartekltg wrote:
>>>  On 01.09.2015 13:20, Richard Heathfield wrote:
>>>>   On 01/09/2015 10:01, David Brown wrote:
>>>>
>>>>   <snip>
>>>>
>>>>>   Yes, you can factorise C by trying to multiply pairs A * B and see if
>>>>>   they match.  The trouble is, with a 600 digit number there are quite a
>>>>>   lot of such pairs to try!
>>>>
>>>>   Well, there aren't all that many really, and the OP specified two
>>>>   300-digit integers, so we needn't bother with lower numbers.
>>>>
>>>>   There are only 9*10^299 300-digit numbers, so we need to test 81*10^598
>>>>   = 8.1*10^599 pairs.
>>>
>>>
>>>  We do not need to check every _pair_, it is enough to
>>>  test if C%A == 0 for any A, so "only" 9*10^299 iterations.
>>
>>  But division is a lot more expensive than multiplication (i.e. it takes
>>  longer to perform the tests).
>
> ...than multiplication by 10^299 numbers?
> No, it is not!
>
> Seriously, are you trolling?

Hanlon's Razor applies. Let me think about it, with smaller numbers!

Okay, so we have two 3-digit primes A and B, and we multiply them 
together to get C. Then Eve gets hold of C. How much work must she do?

There are 143 3-digit primes. If Eve multiplies them, she has to do 
143*143 multiplications, which is 20449. If she does trial division 
instead, she has to divide 143 times, which is clearly *vastly* less 
work (and most especially so when you scale it up to the kind of numbers 
we've been talking about).

Um, when you're right, you're right. But no, I wasn't trolling, just 
being stupid. It happens. (Not *too* often, I hope!) In my defence, it 
was about 2:30am when I posted that article...

-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

[toc] | [prev] | [next] | [standalone]

#5709

W dniu środa, 2 września 2015 11:42:43 UTC+2 użytkownik Richard Heathfield napisał:
> On 02/09/2015 10:24, bartekltg wrote:
> > On 02.09.2015 03:37, Richard Heathfield wrote:
> >>  On 02/09/2015 02:19, bartekltg wrote:
> >>>  On 01.09.2015 13:20, Richard Heathfield wrote:
> >>>>   On 01/09/2015 10:01, David Brown wrote:
> >>>>
> >>>>   <snip>
> >>>>
> >>>>>   Yes, you can factorise C by trying to multiply pairs A * B and see if
> >>>>>   they match.  The trouble is, with a 600 digit number there are quite a
> >>>>>   lot of such pairs to try!
> >>>>
> >>>>   Well, there aren't all that many really, and the OP specified two
> >>>>   300-digit integers, so we needn't bother with lower numbers.
> >>>>
> >>>>   There are only 9*10^299 300-digit numbers, so we need to test 81*10^598
> >>>>   = 8.1*10^599 pairs.
> >>>
> >>>
> >>>  We do not need to check every _pair_, it is enough to
> >>>  test if C%A == 0 for any A, so "only" 9*10^299 iterations.
> >>
> >>  But division is a lot more expensive than multiplication (i.e. it takes
> >>  longer to perform the tests).
> >
> > ...than multiplication by 10^299 numbers?
> > No, it is not!
> >
> > Seriously, are you trolling?
> 
> Hanlon's Razor applies. Let me think about it, with smaller numbers!
> 
> Okay, so we have two 3-digit primes A and B, and we multiply them 
> together to get C. Then Eve gets hold of C. How much work must she do?
> 
> There are 143 3-digit primes. If Eve multiplies them, she has to do 
> 143*143 multiplications, which is 20449. If she does trial division 
> instead, she has to divide 143 times, which is clearly *vastly* less 
> work (and most especially so when you scale it up to the kind of numbers 
> we've been talking about).
> 
> Um, when you're right, you're right. But no, I wasn't trolling, just 
> being stupid. It happens. (Not *too* often, I hope!) In my defence, it 
> was about 2:30am when I posted that article...
> 

anyway someone should for clarity of the thing say how costly is such division of
1e600 number by some 1e300 number - how many partial operations it would contain?

if someone is not able said it for a professional routine maybe for some weaker one? explain how it works - if so this thread could rise to more interesting point (but explaining this is prerequisite)

[toc] | [prev] | [next] | [standalone]

#5710

On 02.09.2015 11:42, Richard Heathfield wrote:

> Hanlon's Razor applies. Let me think about it, with smaller numbers!
>
> Okay, so we have two 3-digit primes A and B, and we multiply them
> together to get C. Then Eve gets hold of C. How much work must she do?

> There are 143 3-digit primes. If Eve multiplies them, she has to do
> 143*143 multiplications, which is 20449. If she does trial division
> instead, she has to divide 143 times, which is clearly *vastly* less
> work (and most especially so when you scale it up to the kind of numbers
> we've been talking about).
>
> Um, when you're right, you're right. But no, I wasn't trolling, just
> being stupid. It happens. (Not *too* often, I hope!) In my defence, it
> was about 2:30am when I posted that article...


;-)

bartekltg

[toc] | [prev] | [next] | [standalone]

#5712

On 02/09/15 11:42, Richard Heathfield wrote:
> On 02/09/2015 10:24, bartekltg wrote:
>> On 02.09.2015 03:37, Richard Heathfield wrote:
>>>  On 02/09/2015 02:19, bartekltg wrote:
>>>>  On 01.09.2015 13:20, Richard Heathfield wrote:
>>>>>   On 01/09/2015 10:01, David Brown wrote:
>>>>>
>>>>>   <snip>
>>>>>
>>>>>>   Yes, you can factorise C by trying to multiply pairs A * B and
>>>>>> see if
>>>>>>   they match.  The trouble is, with a 600 digit number there are
>>>>>> quite a
>>>>>>   lot of such pairs to try!
>>>>>
>>>>>   Well, there aren't all that many really, and the OP specified two
>>>>>   300-digit integers, so we needn't bother with lower numbers.
>>>>>
>>>>>   There are only 9*10^299 300-digit numbers, so we need to test
>>>>> 81*10^598
>>>>>   = 8.1*10^599 pairs.
>>>>
>>>>
>>>>  We do not need to check every _pair_, it is enough to
>>>>  test if C%A == 0 for any A, so "only" 9*10^299 iterations.
>>>
>>>  But division is a lot more expensive than multiplication (i.e. it takes
>>>  longer to perform the tests).
>>
>> ...than multiplication by 10^299 numbers?
>> No, it is not!
>>
>> Seriously, are you trolling?
> 
> Hanlon's Razor applies. Let me think about it, with smaller numbers!
> 
> Okay, so we have two 3-digit primes A and B, and we multiply them
> together to get C. Then Eve gets hold of C. How much work must she do?
> 
> There are 143 3-digit primes. If Eve multiplies them, she has to do
> 143*143 multiplications, which is 20449. If she does trial division
> instead, she has to divide 143 times, which is clearly *vastly* less
> work (and most especially so when you scale it up to the kind of numbers
> we've been talking about).
> 
> Um, when you're right, you're right. But no, I wasn't trolling, just
> being stupid. It happens. (Not *too* often, I hope!) In my defence, it
> was about 2:30am when I posted that article...
> 

You were also inspired by the wording of Fir's suggested algorithm - as
far as I can see, he did want to factor C by trying combinations of A *
B, and thus your calculations for the number of tests needed were correct.

But as seen here, it is a silly way to factorise C - checking C % A for
all possible A is clearly much better (though equally clearly impossible
for current or foreseeable computers).

There are a number of ways of doing this check faster than the
bit-for-bit long division you suggested elsewhere, but it is still slow,
and there are still a lot of numbers to check.

[toc] | [prev] | [next] | [standalone]

#5713

On 02/09/2015 13:12, David Brown wrote:
>
<snip>
>
> There are a number of ways of doing this check faster than the
> bit-for-bit long division you suggested elsewhere,

The advantage of that way is that it's easy to explain, and relatively 
easy to implement. Having said that, I *haven't* implemented it (in 
software). My bignum library uses Algorithm D, from TAOCP II.

>  but it is still slow,
> and there are still a lot of numbers to check.

Since we now know that infinity is "a short while", all we need to do is 
remove the loop test (to make the loop infinite), and then we should 
have the results by, say, tea-time.

-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

[toc] | [prev] | [next] | [standalone]

Page 2 of 3 — ← Prev page 1 [2] 3  Next page →

Back to top | Article view | comp.programming

csiph-web