Prime Number
Russ Housley
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
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
> 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
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
William Unruh
>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
In article <4nb7cv$j...@nntp.ucs.ubc.ca> un...@physics.ubc.ca
>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
> 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
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
In article <KUEHN.96M...@stones.uni-muenster.de>,
ku...@stones.uni-muenster.de says...
>> for the reader. (Hint: the observation that primes larger than 5 are
>> 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
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
David Hill
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
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?
Paul Rubin
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
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
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~}
>>>>> "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
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
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