Cryptography-Digest Digest #991, Volume #9 Thu, 5 Aug 99 14:13:03 EDT
Contents:
Re: Bad Test of Steve Reid's SHA1 ([EMAIL PROTECTED])
Re: The Acronym MDC (Paul Koning)
Re: DES crypt(3) (Paul Koning)
Re: beginner question re. MD5 and one-way hashes (Jerry Coffin)
Re: Prime number. (Bob Silverman)
Re: frequency of prime numbers? (Jim Gillogly)
Re: Good generators and primes for Diffie Hellman (Doug Stell)
Re: Transposition and substitution algorithms ??? (wtshaw)
Re: beginner question re. MD5 and one-way hashes ("Anders J. Munch")
Re: frequency of prime numbers? (Bob Silverman)
Re: DES Algorithm source code (David C. Oshel)
Re: beginner question re. MD5 and one-way hashes (David Wagner)
any literature about trusted unit? ([EMAIL PROTECTED])
Re: Is this a new authent/encrypt protocol? (Greg)
Re: Is this a new authent/encrypt protocol? (Greg)
Re: What is "the best" file cryptography program out there? ([EMAIL PROTECTED])
Re: Americans abroad/Encryption rules? (David C. Oshel)
Re: frequency of prime numbers? (fungus)
Re: frequency of prime numbers? (John Savard)
New Movie Website! ([EMAIL PROTECTED])
Re: frequency of prime numbers? (Robert Scott)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Bad Test of Steve Reid's SHA1
Date: Thu, 05 Aug 1999 14:26:30 GMT
Jerry, thanks again for taking time for a useful and interesting
reply. Believe it or not, I feel that my knowledge is sufficient
enough that I don't have any more questions.
Also, my new SHA1m.dll is working ("m" for minus since I handle only 1-
55-char messages; however, that easily could be changed). If anyone
sends me an e-mail, I would be happy to send a copy of the code.
Rob
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Jerry Coffin) wrote:
> In article <7nste6$ss7$[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
>
> [ ... ]
>
> > So far no-one has told me what LITTLE_ENDIAN does. Does it refer to
> > one of the alternate methods referred to as 7. and 8. on the NTIS
site
> > (thanks to Jerry Coffin for that URL)? I would assume not since,
as D.
> > L. Keever mentions, you do need to define LITTLE_ENDIAN to get the
> > right digest. Or does it refer to the "technical correction" that
> > generated SHA-1 (FIPS 180) in the first place? Something else?
Just
> > curious.
>
> SHA-1 works with 32-bit quantities. On the NTIS site, they assume
> that if you start with bytes like:
>
> 00 01 02 03
>
> and treat them as a single 32-bit quantity, they should end up as:
>
> 00010203
>
> I.e. the first byte becomes the mistyping of the four, and the fourth
> byte ends up as a the least significant. This is what's generally
> referred to as big-endian ordering. By contrast, on a little-endian
> machine, the first byte will end up as the least-significant byte of
> the whole, and the fourth will end up as the most significant. I.e.
> if you take the string above and simply cast a pointer to its
> beginning as a pointer to long, you'll end up with 03020100 as your
> number. Therefore, on a little-endian machine, you have to take the
> inputs and swap them around to produce the right number.
>
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: Paul Koning <[EMAIL PROTECTED]>
Subject: Re: The Acronym MDC
Date: Wed, 04 Aug 1999 14:12:10 -0400
John Savard wrote:
>
> I had thought that MDC stood for Message Digest Code, but according to
> the Handbook of Applied Cryptography, it stands for Modification
> Detection Code!
Neither, according to an old reference I have:
"Proposed federal standard 1027, 5 august 1980
...
3.4.5. ... Manipulation Detection code (MDC) ..."
paul
------------------------------
From: Paul Koning <[EMAIL PROTECTED]>
Subject: Re: DES crypt(3)
Date: Wed, 04 Aug 1999 14:09:05 -0400
[EMAIL PROTECTED] wrote:
>
> Plans are underway to design and build hardware to crack DES crypt(3)
> encoded passwords by brute force using 100MHz Xilix FPGAs in parallel.
> The task is mearly as a "science project" to see just how many possible
> keys we can eliminate / sec. Could someone provide me with the concise
> algorithm for crypt(3). Thanks
"Use the source, Luke"
Pull up a Linux distribution and you can read it.
paul
------------------------------
From: [EMAIL PROTECTED] (Jerry Coffin)
Subject: Re: beginner question re. MD5 and one-way hashes
Date: Thu, 5 Aug 1999 09:41:56 -0600
In article <7oc6q3$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] says...
> dear crypto experts,
>
> I need a one-way function in order to generate hash key values
> for a piece of software that is caching objects i.e. when I come
> across an object the second time the function should generate the
> same hash key so I know that I have seen that object already.
For this, you're only looking for a low-incidence of collisions, not
the other characteristics of a cryptographic hash -- you'd undoubtedly
be better off using a normal CRC instead (there's code available for a
32-bit CRC on www.snippets.org, if you don't have any handy).
Note that this still gives a reasonable chance of a collision -- e.g.
given 200,000 inputs, a 32-bit hash has approximately a 200000/4G =
.005% chance of a collision.
The only way to be reasonably certain of reducing the chances of a
collision is to use a larger harsh -- with a 64-bit hash, your chances
of a collision with 200,000 items drops to approximately 1e-14. Going
to a 128-bit hash, it drops to around 5.8e-34.
Note, however, that no matter how large a hash you use, there's
_always_ a chance of a collision, even in a relatively small set of
objects. As the number of objects goes down and/or the size of the
hash increases, the chances drop, but there's no avoiding the
possibility of a collision, regardless.
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: Prime number.
Date: Thu, 05 Aug 1999 15:19:48 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (John McDonald, Jr.)
wrote:
> On Tue, 03 Aug 1999 23:40:39 GMT, Bob Silverman <[EMAIL PROTECTED]> wrote:
>
> >Bob Silverman
> >"You can lead a horse's ass to knowledge, but you can't make him think"
>
> You know, Bob's response to my post really bothered me for about 10
> minutes today, until I read the rest of his posts to this NG. It
> seems that despite the man's rather costly education, he forgot to
> include people skills. Did you skip the course on "How not to come
> across like an Asshole?" at Harvard? Did they not offer it at the
> University of Chicago?
It is a pretty sure sign that when people start resorting to name calling
that they have nothing constructive to say.
When you and others post assertions in a public forum you have a
responsibility to either be informed about what you are discussing or
to check sources.
This isn't about people skills, it's about responsibility.
Do you react this way to your boss (or professors) when (s)he tells
you that you made a mistake?
>
> Anyways, my point is this. I was incorrect. Someone caught me on it.
> Good for them. No reason to be an asshole.
No, you were NOT merely incorrect. You made a bold assertion
in a public forum which is read by others. As such, it is your
responsibility to see that others who are not knowledgeable in this
subject area are not given false information by your statements.
Did you forget to take the course which teaches how to accept
criticism without resorting to namecalling???
I did not resort to any name calling. I simply criticized your
posting of false and misleading information. And you did not
say "I believe this to be true", you said (in effect) "This is true".
This is not merely making an error. This is not doing your homework
and not meeting your responsibility.
>
> I must say that Bob here is one of the most beligerent people I've
> ever had the misfortune of coming across in all my six years on the
> internet.
Why? Because I make it part of my job to squash nonsense? I spend a lot of
time answering questions. But when someone who clearly has not done even the
basic amount of studying about a subject posts nonsense, I say so.
>Or, rather, the most beligerent who didn't turn out to be a
> pre-pubescent hacker wannabe. Kudos, Bob!
Ah, yes. More namecalling. How mature.
>
> So here's a personal skills lesson for you Bob. It doesn't matter how
> intelligent you are, or how much you actually know. If you come off
> like a conceited, cocky SOB, no one will ever care what you have to
> say.
Here's some lessons for you:
(1) Engage brain before putting mouth into gear. Check your sources
before posting on a subject about which you know very little.
(2) Learn to accept criticism of your posts gracefully. If you are going
to show ignorance in public, expect to be corrected.
(3) Learn not to respond to criticism with name calling and the
usual "you criticized my post, therefore you're an asshole" mantra.
(4) Learn to separate criticism of your POSTS from criticism of you
personally.
Bob Silverman
"You can lead a horse's ass to knowledge, but you can't make him think"
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: frequency of prime numbers?
Date: Thu, 05 Aug 1999 08:43:17 -0700
Bob Silverman wrote:
>
> I wrote:
> > primes, since the remainder modulo each prime is 1. Therefore this
> > number is also prime
>
> NO! NO! NO!
>
> Why must we hear the same tired mistakes over and over?
>
> I have lost count of the number of times I have heard this
> assertion on the Internet.
Oops. Sorry. I guess the answer is "Because this is Usenet."
At least the right proof was posted at about the same time by John
Savard.
Vernor Vinge gives a wonderful portrait of Usenet in "A Fire
Upon the Deep" -- a question gets asked, a bunch of people
jump in with wrong answers, a few have right answers, some are
far out in left field with a totally different mind-set and no clue
whatsoever, and a couple shout "DEATH TO VERMIN!" no matter what's
getting posted.
I'll pause longer before my next post.
--
Jim Gillogly
13 Wedmath S.R. 1999, 15:31
12.19.6.7.11, 3 Chuen 19 Xul, Seventh Lord of Night
------------------------------
From: [EMAIL PROTECTED] (Doug Stell)
Subject: Re: Good generators and primes for Diffie Hellman
Date: Thu, 05 Aug 1999 15:11:24 GMT
On Thu, 05 Aug 1999 07:06:44 GMT, [EMAIL PROTECTED] (David Goodenough)
wrote:
>I have heard that there can exist "bad" generators for DH. What are
>these, and how do I determine if I have one? In a more practical
>vein, is there a quick and easy way to get a good generator?
No generator is better or worse than another, as it is easy to switch
between generators. This is explained in the Handbook of Applied
Cryptography (HAC).
As for what a generator is and how you find one, there is a simple
explaination in Schneier's Applied Cryptography, page 254. Testing
whether a number is a generator or not is easy if you know the
factorization of p-1. Therefore, p is constructed of smaller primes.
>A prime is a prime is a prime, right? I saw in another post a while
>back about "strong" primes, something to do with (p-1)/2 also being
>prime. How much difference (if any) does this make to the security
>provided by DH?
It makes a considerable difference. A discrete log can be calculated
modulo each prime factor of p-1 and these can be combined to find the
discrete log modulo p, using the Chinese Remainder Theorem. The
difficulty of doing this is dominated by the largest prime factor of
p-1. A strong prime of the type you mention guarantees that the
largest prime factor is a large as possible.
doug
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Transposition and substitution algorithms ???
Date: Thu, 05 Aug 1999 10:30:17 -0600
In article <[EMAIL PROTECTED]>, Spike Ivans <[EMAIL PROTECTED]> wrote:
> ... all cryptographic
> systems rely on either or both of two techniques, transposition and
> substitution. So... having said that, I have a few questions...
>
> 1) Is this true ?
If you imply only simple transposition and simple substitution, no. It is
a question of scope since there are times when you know transposition or
substitution is going on, but it surely looks like the mechanism could be
interpreted as either, at least showing that the may be more like two
sides to the same coin.
Then, you have situations in which clear substitution and transposition
steps occur.
But, when you deal with gross changes in format, it is substitution, or
something else? We repeatedly hear the debate here whether compression is
important to crypto. Well, again, it can or it cannot be; it depends on
the scheme, and how it plays when the crypto system is attacked. Formats,
as sets and bases, can be changed.
Encoding, which might also be taken as a form of substitution, but as its
purpose may be more convenience at the plaintext end than increasing
strength at the ciphertext end, its effects might actually make a
cryptosystem weaker. However, it can be used to make a system stronger as
well as it can be used to play with the mind of an attacker.
As an example, considering something I do lots of, adding format
convenience characters, spaces, etc. Surely, the most common character is
the space, and it occurs with some expected frequency. By simply omitting
spaces before encryting, a particular cryptosystem is surely going to be
functionally stronger, but at the cost of the clerk having to redivide
words when plaintext is recovered.
Generally, I present the idea that base changing is too different, from
what is normally categorized as substitution or transposition, to let it
pass as something already included in the classic definitions of what
simple crypto primatives include. Surely, substitution, transposition,
and base changing steps can be combined in a plethora of options to form
new and distinct, if not sometimes useful ciphers.
Something like XOR is clearly another example that fails to fit cleanly
into either category, as it involves a higher level evaluation then simple
substitution or simple transposion, as it requires that encoding step,
which is intimately tied to the idea of bases.
>
> 2) How do modern cryptographic systems implement transposition and
> substitution ?
It all depends on what you mean by modern.
>
> 3) How is the password key used to encrypt data with substitution or
> transposition ?
>
Stickly speaking, a password has a rather narrow definition, that which is
evaluated to allow you to continue on. Password key, your words, implies
that a string is used to make some other key.
It can be hashed by some popular method to present a binary sequence. It
can be hashed by the counting method to produce a string of seeds,
allowing whereever having those can lead. It can be turned into a
permutation string directly, or through a seeded generator. Or it can be
purged of duplicate elements and completed with missing elements to a
required set size to key a number of algorithms.
--
MY lock, MY key.
------------------------------
From: "Anders J. Munch" <[EMAIL PROTECTED]>
Subject: Re: beginner question re. MD5 and one-way hashes
Date: Thu, 5 Aug 1999 18:35:01 +0200
Muharem Hrnjadovic wrote in message
<7oc6q3$[EMAIL PROTECTED]>...
>dear crypto experts,
That's not me, but then I don't think you really need a _cryptographic_ hash
function, you just need a hash function with good distribution.
[...]
>I experimented with MD5 by taking only one quarter of the signature
>it supplies but after a test with ca. 160.000 objects I obtained
>identical values for different objects (which is not MD5's fault
>since I took only 25% of the sequence it calculated).
Actually any subset of a cryptographic hash is a good hash
(distribution-wise); it's just not as _cryptographically_ safe as the full
hash.
Surprisingly, one collision in 160.000 is an excellent result. This is
fewer collisions than you would expect in at set of 160.000 random 32-bit
numbers!
Here's why: Suppose you generate 160.000 truly random numbers. Of these
160.000 numbers you can extract (160.000*159.999)/2 unordered pairs. The
probability that the numbers in any given pair are identical is 1/(2^32).
But since there are (160.000*159.999)/2 different pairs, you will on average
get (160.000*159.999)/2/2^32 = 2,98 collisions.
>
>Can you recommend any other one-way-hash or message digest functions
>that are possibly simpler and generate shorter values?
>
My recommendation: Use 8 bytes instead of 4. For a faster algorithm, a CRC
might be an option. A CRC-64, of course!
- Anders
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: frequency of prime numbers?
Date: Thu, 05 Aug 1999 14:56:29 GMT
In article <[EMAIL PROTECTED]>,
Jim Gillogly <[EMAIL PROTECTED]> wrote:
> Sniggerfardimungus wrote:
> >
> > I ask this question here not because it necessarily relates to cryptography,
> > but to an interest of cryptographers, prime numbers; is there any reason to
> > believe that there are either a finite or an infinite number of primes? Even
> > better, is there any proof either way?
>
> There's an infinite number of them, and an easy proof. Suppose the
> number were finite. Then we can take the product of all the primes
> and add one to it. This number is not evenly divisible by any of the
> primes, since the remainder modulo each prime is 1. Therefore this
> number is also prime
NO! NO! NO!
Why must we hear the same tired mistakes over and over?
I have lost count of the number of times I have heard this
assertion on the Internet.
The resulting number is NOT necessarily prime.
What is true is that EITHER it is prime OR it is divisible by a prime
not on our original list.
--
Bob Silverman
"You can lead a horse's ass to knowledge, but you can't make him think"
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED] (David C. Oshel)
Subject: Re: DES Algorithm source code
Date: Thu, 05 Aug 1999 11:44:48 -0500
In article <[EMAIL PROTECTED]>, fungus
<[EMAIL PROTECTED]> wrote:
> [EMAIL PROTECTED] wrote:
> >
> > In article <7oaf69$[EMAIL PROTECTED]>,
> > "Alberto Daniel Pires dos Barros" <[EMAIL PROTECTED]> wrote:
> > > I'm looking for a DES Algorithm writed in COBOL/400 �any one have it?
> > >
> >
> > Here is a sugestion: DON'T USE DES!
> >
>
> Maybe he doesn't have a choice.
Man, does THAT touch a nerve. Exactly. God save us all from fork-haired
managers.
--
David C. Oshel http://pobox.com/~dcoshel
Cedar Rapids, IA [EMAIL PROTECTED]
``Tension, apprehension and dissension have begun.''
-- Duffy Wyg&, in Alfred Bester's _The Demolished Man_
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: beginner question re. MD5 and one-way hashes
Date: 5 Aug 1999 10:04:11 -0700
In article <[EMAIL PROTECTED]>,
Jerry Coffin <[EMAIL PROTECTED]> wrote:
> Note that this still gives a reasonable chance of a collision -- e.g.
> given 200,000 inputs, a 32-bit hash has approximately a 200000/4G =
> .005% chance of a collision.
Actually, I think it's about 200000^2/2^33 ~ 4 expected collisions.
(Birthday paradox.)
------------------------------
From: [EMAIL PROTECTED]
Subject: any literature about trusted unit?
Date: Thu, 05 Aug 1999 16:37:09 GMT
There are many literatures about "trusted" systems. Is there any study
about how to make today's computer "trusted" by adding a unit, say,
smart card, online service, etc.
Thanks.
Meng
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: Greg <[EMAIL PROTECTED]>
Subject: Re: Is this a new authent/encrypt protocol?
Date: Thu, 05 Aug 1999 16:29:28 GMT
> > Given Elliptic Curve encryption (points are uppercase),
> > Given message m, and its hash h,
> > Given Alice's private key a and public key A,
> > Given Bob's private key b and public key B,
> > Given a base point P,
> >
> > Assume A and B are well known, cannot be spoofed, and are verifiable
> > via alternate means (e.g.- phone call, personal visit).
> >
> > Alice sends message m to Bob by deriving a hash (h) for the message
> > then encrypting it with abhP producing c (cipher text). The secret
S
> > is defined as:
> >
> > S = abhP = ahB = bhA = bJ (J = hA)
> >
> > Alice sends c and J. Bob derives S from bJ, then m from S and c,
> > then h from m. With h, Bob can verify J. That is, haB can only
> > come from Alice.
> >
> > If m is altered, then so also is h and a. Bob would detect this
> > with the decryption process failing.
>
> It took me a bit to figure out what you mean here.
>
> c = E(S,m) is some kind of symmetric cipher, yes?
NO. The protocol says that m, the message to be concealed with ECC, is
encrypted using Alice's private key, Bob's public key, and the hash of
the message.
> Then what you've got is DH plus the hash of the message to create
> the key. This is probably a good thing for similar messages
> assuming the hash is a good randomizer (which most good hashes
> are).
The purpose of the hash is two fold, and I am sorry I did not make
clear WHY I chose the hash. First it acks to authenticate the message
content (I have verified that this works). Second, it acts as a random
value to help hide the secret between messages, thus the public keys
can remain constant over many messages.
> If the keys haven't been verified then it's subject to man-in-
> the-middle attack, just like DH. Adding the hash doesn't really
> improve anything there.
I said this was assumed already.
--
The US is not a democracy - US Constitution Article IV Section 4.
Democracy is the male majority legalizing rape.
UN Security Council is a Democracy. NO APPEALS! Welcome to the NWO.
Criminals=Crime. Armies=Tyranny. The 2nd amendment is about tyranny.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: Greg <[EMAIL PROTECTED]>
Subject: Re: Is this a new authent/encrypt protocol?
Date: Thu, 05 Aug 1999 16:37:57 GMT
> Maybe I'm overlooking something here but....When Alice is encrypting
her
> message to Bob you have her using Bob's private key....thats a Bad
Thing.
> Alice should never know Bob's private key.
I had mentioned that S = abhP = ahB = bhA, so it follows that one
private key, a hash and the public key of the other will always work.
--
The US is not a democracy - US Constitution Article IV Section 4.
Democracy is the male majority legalizing rape.
UN Security Council is a Democracy. NO APPEALS! Welcome to the NWO.
Criminals=Crime. Armies=Tyranny. The 2nd amendment is about tyranny.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: What is "the best" file cryptography program out there?
Date: Thu, 05 Aug 1999 17:26:38 GMT
In article <7oc2gf$14nc$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (SCOTT19U.ZIP_GUY) wrote:
> Paul Onions came up with a "complete chosen file plain text attack"
> at first I did not change my code since I could not see way people
would
> care since it did not help solve the money contest I had at the time.
But
> You and A few others talked my into changaing my mind. Also the
> Diehard Code seemed to show that I had other weaknesses in files with
> an even number of bytes. After much testing I finailly came up with
scott16u
> the major changes besides the Paul routine which seems enough by
itself
> to protect the method was the forced rotation of all files lengths
not just
> the odd file lenghts and the change in the chainning of an XOR for one
> of the additions.
> Scott19u was not tested to the same degree as scott16u but is just
> an extionsion from the 16 bit model of the code to a 19 bit model. It
> runs to slow on my 486 still waiting to buy a K6-3 when the proces
drop.
> but it does run it is just to slow for my taste. The time to build
the tables
> on a fast pentium is about the same as runnung scott16u on my 486
> so when floppies take a jump in size scott23u is not that far away.
> There will be a stability release of scott16u in November or there
abouts
> to change whatever problems people have pointed out and still am
playing
> with the option of adding built in adaptive huffman compression for
those
> that want it. I am using the modified scott16u which has that option
> and it seems to behave nicely as well as one that randomly adds a
garbage
> block of a randomily varying block of padding from 25k to 50k bytes in
> length. However I am not sure what people really want.
So you are jumping from 16 to 19 and now to 23 bit word sizes. May I
ask why? Have you actually investigated the strength of various word
sizes or are you just jumping on what sounds good?
Can't wait till scottu128 comes out!!!
Tom
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED] (David C. Oshel)
Subject: Re: Americans abroad/Encryption rules?
Date: Thu, 05 Aug 1999 11:55:33 -0500
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (JPeschel) wrote:
> I suppose you could call UUencoding a form of encryption in a broad
> sense. Still, if you were teaching a class on encryption, it might
> be better not to consider UUencoding and the like as a subset of
> encryption. Too confusing, I think.
A code is just a map, such as C source -> compiler -> x86 machine code.
Not even necessarily reversible, since you can disassemble x86 machine
code to C source or Pascal source.
You can represent binary numbers in a base 355 system, which you then
represent in a base 113 system, which is a real kick when you store the
output in a binary computer file -- one way to "expand" a file to disguise
its length.
Encryption is a special case of encoding, since it has a social purpose
unrelated to the details of method.
--
David C. Oshel http://pobox.com/~dcoshel
Cedar Rapids, IA [EMAIL PROTECTED]
``Tension, apprehension and dissension have begun.''
-- Duffy Wyg&, in Alfred Bester's _The Demolished Man_
------------------------------
From: fungus <[EMAIL PROTECTED]>
Subject: Re: frequency of prime numbers?
Date: Thu, 05 Aug 1999 19:44:40 +0200
Sniggerfardimungus wrote:
>
> I ask this question here not because it necessarily relates to cryptography,
> but to an interest of cryptographers, prime numbers; is there any reason to
> believe that there are either a finite or an infinite number of primes? Even
> better, is there any proof either way?
>
Yes, there are in infinite number of primes. The proof escapes me at the
moment though.
--
<\___/>
/ O O \
\_____/ FTB.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: frequency of prime numbers?
Date: Thu, 05 Aug 1999 17:54:30 GMT
Bob Silverman <[EMAIL PROTECTED]> wrote, in part:
>The resulting number is NOT necessarily prime.
That's true, however, in sci.math, I've seen proofs worded in such a
way that they appear to contain this mistake.
Actually, you see, IF our previous list contained all the primes, then
our new number would indeed, by not being divisible by any of them,
satisfy the _definition_ of a prime number, not being divisible by any
prime smaller than itself. (Remember, all the primes were on that
list. Supposedly.)
Thus, the original assumption was false, and only after that's
recognized can we consider the possibility of prime numbers, not on
the list, by which that number may be divisible.
Thus, in the formal _reductio ad absurdum_ version of the proof, the
statement that the new number is itself prime _as a consequence of the
assumptions, which include a false statement_ appears, even though in
the real world the product of a bunch of primes plus 1 does not have
to be prime.
So this is what has led to less formal versions of the proof floating
around which contain a fallacy.
John Savard ( teneerf<- )
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED]
Subject: New Movie Website!
Date: Thu, 05 Aug 1999 17:18:17 GMT
New Entertaining Movie Game Website!
http://www.moviedoubletakes.com
Totally free!! Test your knowledge!!
(Uh^$
------------------------------
From: [EMAIL PROTECTED] (Robert Scott)
Subject: Re: frequency of prime numbers?
Reply-To: [EMAIL PROTECTED]
Date: Thu, 05 Aug 1999 17:56:53 GMT
>In article <[EMAIL PROTECTED]>,
> Jim Gillogly <[EMAIL PROTECTED]> wrote:
>>
>> There's an infinite number of them, and an easy proof. Suppose the
>> number were finite. Then we can take the product of all the primes
>> and add one to it. This number is not evenly divisible by any of the
>> primes, since the remainder modulo each prime is 1. Therefore this
>> number is also prime
>
>
To which Bob Silerman responded:
>NO! NO! NO!
>
>Why must we hear the same tired mistakes over and over?
>
>I have lost count of the number of times I have heard this
>assertion on the Internet.
>
>The resulting number is NOT necessarily prime.
>
>What is true is that EITHER it is prime OR it is divisible by a prime
>not on our original list.
>
No, no, no to you, Bob. There was nothing wrong with Jim's
proof. You just forgot the context. He said "suppose the
number were finite". This is a typical instance of proof
by contradiction. Under the assumption that there are only
finitely many primes, the conclusion that the product of
all of them plus one is prime is correct. There would be no
other primes "not on the list". The fact that this leads
to a contradiction shows that the original assumption
(of finitely many primes) was incorrect. This proof as
stated by Jim in no way implies that the product of any
particular set of primes plus one is itself a prime.
Stick by your guns, Jim. No need to apologize.
Bob Scott
Ann Arbor, Michigan (email: rscott (at) wwnet (dot) net )
(My automatic return address is intentionally invalid.)
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
