Prev: reverse use of encryption and decryption
Next: Finding PGP key with known cleartext
From: Noob on 5 Jan 2010 07:57
Hello,

[ This is only moderately related to sci.crypt ]

http://bellard.org/pi/pi2700e9/

On December 31st, 2009, about 2700 billion decimal digits of Pi
were computed using a single desktop computer. This is presently
the World Record for the computation of Pi.

The author's FAQ mentions

"""
Which book should I read to learn arbitrary-precision arithmetic?
* Modern Computer Arithmetic by Richard Brent and Paul Zimmermann, version 0.4, November 2009.
* The Art of Computer Programming, volume 2 : Seminumerical Algorithms by Donald E. Knuth, Addison-Wesley, third edition, 1998.
"""

Would you recommend others?

Regards.
From: Thomas Pornin on 5 Jan 2010 08:36
According to Noob <root(a)127.0.0.1>:
> The author's FAQ mentions
>
> """
> Which book should I read to learn arbitrary-precision arithmetic?
> * Modern Computer Arithmetic by Richard Brent and Paul Zimmermann,
> version 0.4, November 2009.
> * The Art of Computer Programming, volume 2 : Seminumerical Algorithms
> by Donald E. Knuth, Addison-Wesley, third edition, 1998.
> """
>
> Would you recommend others?

In the context of cryptography, you may want to look at the Handbook of
Applied Cryptography, especially the chapter 14. It can be downloaded
for free there:
http://www.cacr.math.uwaterloo.ca/hac/

Also, the "Guide to Elliptic Curve Cryptography" (Hankerson, Menezes,
Vanstone) contains quite detailed information (chapters 2 and 5).


These mainly deal with the "short numbers", which individually fit in
the L1 cache of a standard CPU. For very big integers, you have to
deal with locality issues, which these books do not cover (and that is
a big part of Bellard's recent work).


--Thomas Pornin
From: rossum on 5 Jan 2010 08:46
On Tue, 05 Jan 2010 13:57:02 +0100, Noob <root(a)127.0.0.1> wrote:

>Hello,
>
>[ This is only moderately related to sci.crypt ]
>
>http://bellard.org/pi/pi2700e9/
>
>On December 31st, 2009, about 2700 billion decimal digits of Pi
>were computed using a single desktop computer. This is presently
>the World Record for the computation of Pi.
>
>The author's FAQ mentions
>
>"""
>Which book should I read to learn arbitrary-precision arithmetic?
>* Modern Computer Arithmetic by Richard Brent and Paul Zimmermann, version 0.4, November 2009.
>* The Art of Computer Programming, volume 2 : Seminumerical Algorithms by Donald E. Knuth, Addison-Wesley, third edition, 1998.
>"""
>
>Would you recommend others?
>
>Regards.
Prime Numbers by Crandall and Pomerance.

rossum

From: Phil Carmody on 5 Jan 2010 20:03
Noob <root(a)127.0.0.1> writes:
> Hello,
>
> [ This is only moderately related to sci.crypt ]
>
> http://bellard.org/pi/pi2700e9/
>
> On December 31st, 2009, about 2700 billion decimal digits of Pi
> were computed using a single desktop computer. This is presently
> the World Record for the computation of Pi.
>
> The author's FAQ mentions
>
> """
> Which book should I read to learn arbitrary-precision arithmetic?
> * Modern Computer Arithmetic by Richard Brent and Paul Zimmermann, version 0.4, November 2009.
> * The Art of Computer Programming, volume 2 : Seminumerical Algorithms by Donald E. Knuth, Addison-Wesley, third edition, 1998.
> """
>
> Would you recommend others?

For multi-precision arithmetic, usually I recommend /Prime Numbers,
a Computational Perspective/ by Crandall & Pomerance. However, I
wonder if, like Kanada discovered, the FFT techniques in PNaCP don't
apply perfectly due to I/O overheads making the FFTs more wasteful.

You'll rarely go wrong by studying anything by Brent/Zimmermann
though - it the above doesn't have what you need, then it almost
certainly has pointers to what you need.

Phil
--
Any true emperor never needs to wear clothes. -- Devany on r.a.s.f1
 | 
Pages: 1
Prev: reverse use of encryption and decryption
Next: Finding PGP key with known cleartext