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

Dismiss

19 views

Skip to first unread message

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

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

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.

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

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?

|>

The largest prime number below 2^128 is

2^128-159 = 340282366920938463463374607431768211297

= 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF61

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

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

to

>The largest prime number below 2^128 is

>2^128-159 = 340282366920938463463374607431768211297

> = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF61

This is known, or probable?

--

Bill Unruh

un...@physics.ubc.ca

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:

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

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

to

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

+---------------+----------------------------+--------------------------+

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

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

to

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

ku...@stones.uni-muenster.de says...

>> Generalising this to more compact representations is left as an exercise

>> for the reader. (Hint: the observation that primes larger than 5 are

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

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

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

to

In article <KUEHN.96M...@stones.uni-muenster.de> ku...@stones.uni-muenster.de (Ulrich Kuehn) writes:

> 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

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

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?

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.

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.

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.

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

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

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

0 new messages

Search

Clear search

Close search

Google apps

Main menu