Prime Number

18 views
Skip to first unread message

Russ Housley

unread,
May 14, 1996, 3:00:00 AM5/14/96
to

I am looking for the largest prime number that can be stored in 128
bits (two words on a Digital Alpha). Can anyone tell me the answer?

Thanks in advance,
Russ
hou...@spyrus.com


Richard Pinch

unread,
May 14, 1996, 3:00:00 AM5/14/96
to

In article <4n8fuo$2...@news6.erols.com> hou...@spyrus.com (Russ Housley) writes:
>I am looking for the largest prime number that can be stored in 128
>bits (two words on a Digital Alpha). Can anyone tell me the answer?

2^127 - 1 if you're using signed integers: 2^128 - 159 unsigned.

Richard Pinch; Queens' College, Cambridge


Paul Leyland

unread,
May 14, 1996, 3:00:00 AM5/14/96
to

In article <4na6cg$p...@lyra.csx.cam.ac.uk> rg...@can.pmms.cam.ac.uk (Richard Pinch) writes:

> In article <4n8fuo$2...@news6.erols.com> hou...@spyrus.com (Russ Housley) writes:
> >I am looking for the largest prime number that can be stored in 128
> >bits (two words on a Digital Alpha). Can anyone tell me the answer?
>
> 2^127 - 1 if you're using signed integers: 2^128 - 159 unsigned.

Given that almost all primes are odd, you can store [p/2] and reach the
second value with signed ints. Treat the value 0 as representing the
prime 2. With this representation, the largest prime you can reach with
unsigned integers is 2^129 - 25.

Generalising this to more compact representations is left as an exercise
for the reader. (Hint: the observation that primes larger than 5 are
all of the form 30k+1,7,11,13,17,19,23,29 has been exploited on
byte-addressable machines.)


Paul

--
Paul Leyland <p...@oucs.ox.ac.uk> | Hanging on in quiet desperation is
Oxford University Computing Services | the English way.
13 Banbury Road, Oxford, OX2 6NN, UK | The time is gone, the song is over.
Tel: +44-1865-273200 Fax: 273275 | Thought I'd something more to say.
PGP KeyID: 0xCE766B1F

Richard Schroeppel

unread,
May 14, 1996, 3:00:00 AM5/14/96
to

In article <4n8fuo$2...@news6.erols.com>, hou...@spyrus.com (Russ Housley) writes:
|> I am looking for the largest prime number that can be stored in 128
|> bits (two words on a Digital Alpha). Can anyone tell me the answer?
|>
|> Thanks in advance,
|> Russ
|> hou...@spyrus.com
|>

The largest prime number below 2^128 is

2^128-159 = 340282366920938463463374607431768211297

= 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF61

Rich Schroeppel r...@cs.arizona.edu


William Unruh

unread,
May 15, 1996, 3:00:00 AM5/15/96
to

In <4namu3$1...@optima.cs.arizona.edu> r...@cs.arizona.edu (Richard Schroeppel) writes:


>The largest prime number below 2^128 is

>2^128-159 = 340282366920938463463374607431768211297

> = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF61


This is known, or probable?
--
Bill Unruh
un...@physics.ubc.ca

Peter L. Montgomery

unread,
May 15, 1996, 3:00:00 AM5/15/96
to

In article <4nb7cv$j...@nntp.ucs.ubc.ca> un...@physics.ubc.ca
(William Unruh) writes:
>In <4namu3$1...@optima.cs.arizona.edu> r...@cs.arizona.edu
> (Richard Schroeppel) writes:

>>The largest prime number below 2^128 is

>>2^128-159 = 340282366920938463463374607431768211297

>> = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF61

>This is known, or probable?

Numbers around 2^128 are easy to prove prime (if they are indeed prime).
If p = 2^128 - 159, then

p - 1 = 2^5 * 3 * 10253 * 29333 * 4454477 * 42113237 * 62826870453001

We prove (recursively) that each factor on the right is prime,
and find elements of orders 10253, 29333, ... in
the multiplicative group mod p-1.
--
Peter L. Montgomery pmon...@cwi.nl San Rafael, California

My sex is male. I am ineligible for an abortion.

Ulrich Kuehn

unread,
May 17, 1996, 3:00:00 AM5/17/96
to

In article <PCL.96Ma...@sable.ox.ac.uk> p...@sable.ox.ac.uk (Paul Leyland) writes:

> Generalising this to more compact representations is left as an exercise
> for the reader. (Hint: the observation that primes larger than 5 are
> all of the form 30k+1,7,11,13,17,19,23,29 has been exploited on
> byte-addressable machines.)
>
>

Can You give a proof for that?

Regards,
Ulrich
--
--
+---------------+----------------------------+--------------------------+
| Ulrich Kuehn | Internet: | Two wrongs do not make a |
| Dipl.-Math. | ku...@math.uni-muenster.de | right but three lefts do |
+---------------+----------------------------+--------------------------+


David Drysdale

unread,
May 17, 1996, 3:00:00 AM5/17/96
to

Ulrich Kuehn (ku...@stones.uni-muenster.de) wrote:
: In article <PCL.96Ma...@sable.ox.ac.uk> p...@sable.ox.ac.uk (Paul Leyland) writes:

: > all of the form 30k+1,7,11,13,17,19,23,29 has been exploited on


: > byte-addressable machines.)
: >
: >
: Can You give a proof for that?

Number of Form Divisible by
30k+0 3
30k+1 XX
30k+2 2
30k+3 3
30k+4 2
30k+5 5
30k+6 2
30k+7 XX
30k+8 2
30k+9 3
30k+10 2
30k+11 XX
30k+12 2
30k+13 XX
30k+14 2
30k+15 5
30k+16 2
30k+17 XX
30k+18 2
30k+19 XX
30k+20 2
30k+21 3
30k+22 2
30k+23 XX
30k+24 2
30k+25 5
30k+26 2
30k+27 3
30k+28 2
30k+29 XX

Bill Wade

unread,
May 17, 1996, 3:00:00 AM5/17/96
to

In article <KUEHN.96M...@stones.uni-muenster.de>,
ku...@stones.uni-muenster.de says...

>
>In article <PCL.96Ma...@sable.ox.ac.uk> p...@sable.ox.ac.uk (Paul
Leyland)
>writes:
>
>> Generalising this to more compact representations is left as an exercise
>> for the reader. (Hint: the observation that primes larger than 5 are
>> all of the form 30k+1,7,11,13,17,19,23,29 has been exploited on
>> byte-addressable machines.)
>>
>>
>Can You give a proof for that?

All integers can be represented as 30k + some number between 0 and 29.

30k+2j is divisible by 2
30k+3j is divisible by 3
30k+5j is divisible by 5

Removing multiples of 2,3,5 from 0,,,29 gives 1,7,11,13,17,19,23,29


Ulrich Kuehn

unread,
May 20, 1996, 3:00:00 AM5/20/96
to

> In article <PCL.96Ma...@sable.ox.ac.uk> p...@sable.ox.ac.uk (Paul Leyland) writes:
>
> > Generalising this to more compact representations is left as an exercise
> > for the reader. (Hint: the observation that primes larger than 5 are
> > all of the form 30k+1,7,11,13,17,19,23,29 has been exploited on
> > byte-addressable machines.)
> >
> >
> Can You give a proof for that?
>

Sorry for quoting myself, I did not think enough before posting...
Maybe I thought it should be the other way around, that all numbers
of the given form are prime, but that is not whats written there....

Mea culpa

David Hill

unread,
May 21, 1996, 3:00:00 AM5/21/96
to

if 30k+19 is a prime number then what about 49 been divided by 7
ie 7*7=49

Could you clarify this for me

Siva Chander

unread,
May 21, 1996, 3:00:00 AM5/21/96
to

Richard Schroeppel (r...@cs.arizona.edu) wrote:

: The largest prime number below 2^128 is

: 2^128-159 = 340282366920938463463374607431768211297

: Rich Schroeppel r...@cs.arizona.edu

Wow! The man who discovered the sub-exponential sieves himself!

Just a quick historical question: Given that Morrison & Brillhart were
already trying to factor quadratic residues using CFRAC, were you aware
of the possibility of factoring 'small' quadratic residues using your sieve
(i.e. Pomerance's simplification) or did you just inexplicably overlook
the possibility?

si...@emi.net

Paul Rubin

unread,
May 22, 1996, 3:00:00 AM5/22/96
to

Nobody said 30k+19 is *always* a prime number. Just that if N
is a prime number, it is always of the form 30k+a, where a might
be 1, 19, or certain other numbers. For example, 30k+3 is *never* prime.

Paul Leyland

unread,
May 22, 1996, 3:00:00 AM5/22/96
to

In article <5167cc$a149.232@TOKE> David Hill <hi...@lincoln.ac.nz> writes:

> if 30k+19 is a prime number then what about 49 been divided by 7
> ie 7*7=49
>
> Could you clarify this for me

Re-read what I said. All primes larger than 5 are of the form
30k+1,7,11,13,17,19,23,29


I did *not* say that all numbers of that form are prime.

Ulrich Kuehn

unread,
May 28, 1996, 3:00:00 AM5/28/96
to

In article <5167cc$a149.232@TOKE> David Hill <hi...@lincoln.ac.nz> writes:

> if 30k+19 is a prime number then what about 49 been divided by 7
> ie 7*7=49
>
> Could you clarify this for me
>

I tapped into the same trap: the original poster did NOT say, that
all numbers of the form 30k+j for some special j (I try to remember,
that might be j=3,5,7,11,13,17,19,23,29, but I might be wrong)
are primes. That is simply wrong. What he did say is, that if a
number is prime, it is expressible in such a form. That is the other
way around.

Lee Sau Dan ~{@nJX6X~}

unread,
May 31, 1996, 3:00:00 AM5/31/96
to

>>>>> "Ulrich" == Ulrich Kuehn <ku...@stones.uni-muenster.de> writes:

Ulrich> I tapped into the same trap: the original poster did NOT
Ulrich> say, that all numbers of the form 30k+j for some special j
Ulrich> (I try to remember, that might be
Ulrich> j=3,5,7,11,13,17,19,23,29, but I might be wrong) are
Ulrich> primes. That is simply wrong. What he did say is, that if
Ulrich> a number is prime, it is expressible in such a form. That
Ulrich> is the other way around.

Right! The formula just gives possible *candidates* of prime numbers.
It doesn't verify if a number is prime.

The values of j should be 7,11,13,17,19,23,29. Note that
30k+3=3(10k+1) is divisible by 3 and 30k+5=5(6k+1) is divisible by 5.

Another similar formula is 6k+j, where j=+-1.

The simples formula of this form is 2k+1.

--
Lee Sau Dan

-------------------------------------------------------------------------------
URL: http://www.cs.hku.hk/~sdlee
e-mail: sd...@cs.hku.hk

Rick Heylen

unread,
Jun 1, 1996, 3:00:00 AM6/1/96
to

In article <SDLEE.96M...@ipc21.cs.hku.hk>,

Lee Sau Dan ~{@nJX6X~} <sd...@cs.hku.hk> wrote:
>Right! The formula just gives possible *candidates* of prime numbers.
>It doesn't verify if a number is prime.
>
>The values of j should be 7,11,13,17,19,23,29. Note that
>30k+3=3(10k+1) is divisible by 3 and 30k+5=5(6k+1) is divisible by 5.

Oh dear! And to think that all this time I thought that 31 was prime.

There are eight values of j as phi(30)=8 . They are the numbers where
gcd(30,j)=1

Rick

--
All I could see was the B-side of the disc which had assumed an oval shape
with the label on the outside rim.
I reached for the arm, which was less than one micron long, yet weighed
more than Saturn, and time stood still...
PGP key 512/CA5CADED Fingerprint= 0000000000 65AB 2F76 EBEF F79C 10FA 88


benjamin t grover

unread,
Jun 21, 1996, 3:00:00 AM6/21/96
to

BTW- There is NO formula which will be all primes.


David Hill (hi...@lincoln.ac.nz) wrote:
: if 30k+19 is a prime number then what about 49 been divided by 7

Reply all
Reply to author
Forward
0 new messages