Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

# Prime Number

19 views

### Russ Housley

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?

Russ
hou...@spyrus.com

### Richard Pinch

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

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

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

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?
|>
|> 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

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

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

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
>
>

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

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

: >
: >
: 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

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
>>
>>
>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

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
> >
> >
> 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

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

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
(i.e. Pomerance's simplification) or did you just inexplicably overlook
the possibility?

si...@emi.net

### Paul Rubin

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

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

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~}

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

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