Cryptography-Digest Digest #754, Volume #10 Fri, 17 Dec 99 13:13:01 EST
Contents:
Re: 8192bit Encrypt - Easy ! (Adam Lock)
Cryptologia journal ([EMAIL PROTECTED])
Re: Breaking a cipher. (John Savard)
Re: Keystrokes monitored/encryption useless (CLSV)
Re: Cryptologia journal (David A Molnar)
Re: More idiot "security problems" (Eric Lee Green)
Re: Breaking a cipher. (Keith A Monahan)
Re: Keystrokes monitored/encryption useless (Guy Macon)
Re: Reducing Key Sizes (Tom St Denis)
Re: Questions about message digest functions (Tim Tyler)
Re: More idiot "security problems" (Jerry Coffin)
Re: More idiot "security problems" (Jeff Williams)
Re: Breaking a cipher. (Tom St Denis)
First step in finding primes (Tom St Denis)
Re: The Cracking of SecurityPlus! 4.32 (Troed)
Re: DES key safety (Jerry Coffin)
Re: First step in finding primes (Scott Fluhrer)
Re: First step in finding primes (Tom St Denis)
----------------------------------------------------------------------------
From: Adam Lock <[EMAIL PROTECTED]>
Subject: Re: 8192bit Encrypt - Easy !
Date: Fri, 17 Dec 1999 15:21:29 +0000
Glen Bridgland wrote:
> Hi, I new to the group however, I hope to be sharing a lot with the Users
> here over the next few months as I finalise my Project. I am current
> developing an encryption program that will offer 8192bit Encryption along
> with a host of features.
8192bit encryption is only any use for someone prepared to remember a 1024
byte or greater key.
--
Adam Lock
------------------------------
From: [EMAIL PROTECTED]
Subject: Cryptologia journal
Date: Fri, 17 Dec 1999 15:26:57 GMT
I would like to acquire all back issues of
Cryptologia, but I cannot afford the $ 12.00 per
piece� !
And a good number is out-of-print.
Is there someone that would have them available ?
Thanks
Jean
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Breaking a cipher.
Date: Fri, 17 Dec 1999 08:51:12 GMT
"jim" <[EMAIL PROTECTED]> wrote, in part:
>I'm only a newbie to the world of cryptography and I was wodering about
>breaking a cipher. Is it a hard task,
Yes, it is, because
>or is it just reversing the cipher
>and using as many keys as possible?
if the cipher is any good, there are too many keys to try for this to
be a sensible way to try and break it. (However, it is also true that
"if the cipher is any good", this should be the only way left, because
there should not be any cryptanalytic weaknesses.)
John Savard (jsavard<at>ecn<dot>ab<dot>ca)
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: CLSV <[EMAIL PROTECTED]>
Subject: Re: Keystrokes monitored/encryption useless
Date: Fri, 17 Dec 1999 15:53:17 +0000
"SCOTT19U.ZIP_GUY" wrote:
> [EMAIL PROTECTED] (Bauerda) wrote:
> > [..] Before I upgraded to Windows, I had my startup files set so that they traced a
> "upgraded to Windows" if this is nat a bastardtisetion of the English
> language I don't know what is.
:-)
Wow, this lack of beer as you mentioned earlier is
a very positive thing.
Regards,
CLSV
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Cryptologia journal
Date: 17 Dec 1999 15:57:05 GMT
[EMAIL PROTECTED] wrote:
> And a good number is out-of-print.
> Is there someone that would have them available ?
You might try looking for libraries in your area. A local library
should have the resources to search for the nearest archive. Plus they
may be able to get a specific issue for you via inter-library loan.
If you search on the Web, you should be able to find the tables of
contents; this may help you pick out the issues you want.
Good luck,
-David Molnar
------------------------------
From: Eric Lee Green <[EMAIL PROTECTED]>
Subject: Re: More idiot "security problems"
Date: Fri, 17 Dec 1999 09:09:56 -0700
Xcott Craver wrote:
> Eric Lee Green <[EMAIL PROTECTED]> wrote:
> >Let's get this straight. Those passwords are sent across the network IN PLAIN
> >TEXT every time that the user logs into an IMAP or POP3 EMAIL server, and you
> >can but this "security expert" at "Reliable Software Technologies Corp."
> >(hmm, is this a one-man outfit?) doesn't ever mention that, instead focusing
> >on how the keys are stored in the registry?
>
> Firstly, the way the keys are stored in the registry allow the
> passwords to be stolen even if you never use your IMAP or POP3
> account.
True Story: Once upon a time, in a land far far away, I was one of those kids
who stripped copy protection off of games. I was irritated that I couldn't run
games off of a decent disk drive and instead was stuck running them off of
slow floppy drives that the copy protection always made bang and burp and run
like crud. I'm talking about, some games that would load in 10 seconds off of
a hard drive took THREE MINUTES to load off of floppy! Game makers tried all
kinds of tricks to stop me and my ilk, such as, e.g., encrypting their
encryption code with one key, then the decrypted code contained yet another
key to decrypt another entire block of encryption code, etc., etc., but I
always got my man. The reason? No program is immune to a good debugger (and by
the end, what finally got game makers to give up on copy protection, HARDWARE
ASSISTED debuggers marketed at crackers were pretty darned cheap!).
The lesson that I gained from that is that all "encryption" which relies upon
having a decryption key buried in the code is insecure.
Years later, I asked a program's author why he used a simple XOR mask to hide
some data on disk. Said he, "anybody who really wanted that data could get it
anyhow" (by reverse-engineering the software that UN-hides the data in order
to pull out the key). His point was that all he cared about was keeping casual
onlookers from viewing the data, and that he didn't see the point in putting a
better encryption algorithm into his program when any hacker worth his salt
could run his program through a binary debugger and decrypt his data, no
matter how good his encryption algorithm.
The point, the point: Netscape could have used 3DES to encrypt the password
stored in the registry, but the fact of the matter is that it has to be
decrypted to plain text in order to pass via IMAP. What that means is that the
decryption key has to be stored somewhere, either in the Netscape program text
or whatever. David Wagner proved in his cryptanalysis of the Netscape 1.0 SSL
code that it's possible to run even a program as huge as Netscape through a
binary debugger and gain critical insight into its security (he found they had
a buggy PRNG, btw, though that has been fixed since). So any hacker could get
the decryption key needed to decrypt the password stored in the registry -- no
matter what the algorithm used.
I suspect that Netscape using a simple XOR mask is for the same reason as why
that other programmer used a simple XOR mask -- because, since the key had to
be stored as part of his program and was accessible to anybody who knew how to
run a binary debugger, doing more would have been a waste of his time. The
whole point of the "encryption" is to prevent viewing by casual onlookers --
NOT to prevent the password from being decrypted. Because that's a lost cause
-- I guarantee you that if Netscape had used 3DES to encrypt that password, I
could *STILL* have decrypted the password, simply by stepping through Netscape
until I found the portion of the code that decrypted the key, finding the
place inside Netscape where the key was stored, and then duplicate that code
and decryption key into a stand-alone "decode all Netscape passwords
everywhere".
And I'm not a so-called "security expert". No wonder I have nothing but
disdain for the "security expert" who discovered this "security problem".
The *ONLY* way to keep stored data secure is to require the user to type a
password or passphrase in order to encrypt and/or decrypt it. If the
decryption key itself is stored on the hard drive, a simple XOR mask is just
as secure as 256-bit Twofish, because the security of the encryption algorithm
now boils down to "dig out the password out of the program's code".
> Secondly, The real newsmaker for us is not the fact
> that it is insecure, or the least secure link in the chain, but
> that the encryption scheme used is unbelievably, hilariously bad.
See my discussion above.
> >So exploiting this requires physical access to the machine.
>
> It does not necessarily require physical access to the machine,
> just a computer program that can read the registry and pass the
> data back.
Okay, so exploiting it requires either a) physical access to the machine, or
b) you've already breached the machine's security in order to install a
program remotely on his machine. Either way, it doesn't matter whether the
EMAIL password was encrypted with a simple XOR mask or with 3DES, that guy is
toast.
Again, the only real lesson here is:
Don't use the same password for your EMAIL that you use for your login!
Which any real security expert could have already told you, since those
passwords are being passed over the network as PLAIN TEXT (required by POP3
and IMAP protocols), and can be intercepted by anybody who can download a
network scanner from one of the "hacker" sites -- no physical access or breach
of security required.
-- Eric Lee Green http://members.tripod.com/e_l_green
[EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED] (Keith A Monahan)
Subject: Re: Breaking a cipher.
Date: 17 Dec 1999 16:23:43 GMT
Jim,
It depends on what cipher you are talking about. If you are talking
about breaking the cipher used to encrypt ZIP files built-in to PKZIP,
it is very easy. If you are talking about breaking PGP, that is another
story. There are plenty of easy ciphers to break and plenty of hard
ciphers we can't.
Overall, remember, most serious cipher designers build ciphers specifically
to withstand cryptanalysis. So this means, they are trying to make it
a hard task to break it. As far as trying as many keys as possible,
this may work if one of two things is true. If your victim is not crypto
savvy, uses his dog's name or his mom's name for a password, etc -- then a
dictionary attack should work fine. The only other way you can brute
force the key is if the keyspace is short. Most modern ciphers aren't going
to fall into that category.
This is a little watered down, but it should give you a general idea of
what you are up against.
An interesting web page http://user.aol.com/jpeschel/index.htm run by
Joe Peschel is a good place to start.
Or if you want to read in alot more detail, Applied Cryptography by Bruce
Schneier is the defacto standard text.
Keith
jim ([EMAIL PROTECTED]) wrote:
: I'm only a newbie to the world of cryptography and I was wodering about
: breaking a cipher. Is it a hard task, or is it just reversing the cipher
: and using as many keys as possible?
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: Keystrokes monitored/encryption useless
Date: 17 Dec 1999 11:55:27 EST
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Johnny Bravo)
wrote:
> Just for laughs I let a friend of mine access my computer in this
>way and turned my protection software off. For most of a night we
>played around with it, he took control of my keyboard and mouse and
>commented on the pictures I was editing with a pop up message box.
>From his point of view, he was sitting at my computer.
>
> The only thing I could do to stop it was turn the computer off
>(ctrl-alt-delete was disabled), and not reconnect to the internet
>until I found the offending program. It wasn't hard, I didn't even
>need AtGuard to do so. The program was being called from the win.ini
>file upon startup
Back Orifice can be installed so as to be difficult to detect.
Try again using the obfuscation methods in the manual.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Reducing Key Sizes
Date: Fri, 17 Dec 1999 16:55:19 GMT
In article <83dhln$23oo$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (SCOTT19U.ZIP_GUY) wrote:
> In article <[EMAIL PROTECTED]>, "Adam Pridmore"
<[EMAIL PROTECTED]> wrote:
> >Does anyone know if there are any security issues in symmetric
algorithms if
> >the key size is reduced (eg making the last x bits of the key
constant),
> >other than reducing the number of available keys. (ie Brute force is
still
> >the easiest way to break it).
> Of course keeping a portion of the key constand reduces the
possible
> set of mappings so yes this does make a it easier to break.
> >
> >Could this be very dependant on the algorithm chosen?
>
> Of course it would depend on the algorithm chosen why
> are you asking such obvious questions. Spit it out man
> what are you driving at.
It depends almost always linearly on the speed of the cipher(s) in this
case. One cipher may be x, and another 2x (time taken to decrypt). So
the latter is twice as hard to brute force.
I do this in Peekboo to allow some ciphers use the 160 bit keys.
Twofish for example takes 128/192/256 bit keys so the upper 32 bits are
zeroed. Does this make it weak? No. [relative to a brute force attack]
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Questions about message digest functions
Reply-To: [EMAIL PROTECTED]
Date: Fri, 17 Dec 1999 16:56:28 GMT
James Felling <[EMAIL PROTECTED]> wrote:
: Tim Tyler wrote:
:> wtshaw <[EMAIL PROTECTED]> wrote:
:> : In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] wrote:
:> :> wtshaw <[EMAIL PROTECTED]> wrote:
:> : Since you asked, I resolve a portion of my comment: collisions and
:> : security of a hash function work in opposition, no collisions meaning
:> : that the input can be solved, be that perhaps inconvenient. But, if
:> : lots rode on the solution, it might be worth it.
:> Surely collision resistance and security are generally positively
:> connected - rather than negatively.
: Simply put, in a hash both are desirable properties.
Yes, indeed.
: Ideally youur hash should be as collision resistant as possible. Ideally
: it should also be resistant to being worked backward (if every message
: has a unique hash this can be a problem as far as keeping the messages
: secure).
Can it? How?
This can only happen if hash-size = message size. The alternative is to
give some messages the same hash as one another. This makes little
difference to the ability to locate the hash for any given message, but
makes collisions infinitely more probable :-(
: However, pursuing any one of them is a bad thing.
/How/ is pursuing collision resistance a bad thing?
*Ignoring* the difficulty of reversing the hash /would/ be a bad thing.
But "one-way"ness does not require increased probability of hash
collisions as far as I can see.
: XORing the message with a fixed key/ permuting it with a fixed permutation
: is completely resistant to collision [...]
This is only possible if hash size = message size, of course.
[...] but is horribly insecure [...]
Yes. For one thing, this is not a one-way function.
: [...] and maping all values to 1 of 4 values is very resistant to being
: worked backward [...]
No. It's likely to be trivial to "work backwards":
Validate the hashes on a few messages - until the values of all four
hashes are known.
Then append these four hashes in turn to your target message. One of them
will validate as being correct. You don't need the private information
about the primes (or whatever) that are used to generate the hash in order
to be able to do this.
This attack can be applied in a large number of the cases where hashes are
applied in practice.
: One must seek to maximize both and remain aware that when it gets down
: to it, there are tradeoffs that must occur.
Tradeoffs are not required. Collision resistance and security do not
pull in opposed directions.
I'll qualify this. Look at the attack that minimal collision-resistance
leads to in the case when message size = hash size:
Having a message (of the same length as the hash) with a correct hash
gives the attacker information that no other messages (again of the same
length of the hash) do not have this hash.
The attacker would not have this information if the hash simulated a
genuinely random function.
This attack /could/ conceivably lead somewhere if most possible
messages of that length had had their hashes discovered - except
the one in question.
These circumstances are pretty unlikely.
To think that eliminating this attack by removing this information - and
consequently opening the door for random hash collisions - is worth it
seems to me to be utterly fantastic.
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
A good traveller leaves no track.
------------------------------
From: [EMAIL PROTECTED] (Jerry Coffin)
Subject: Re: More idiot "security problems"
Date: Fri, 17 Dec 1999 10:16:00 -0700
In article <83d349$81j$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] says...
[ ... ]
> But I was looking for the more general term for a coder
> developing a hilariously awful algorithm for a basic problem
> that can only come from (a) complete ignorance of existing
> algorithms; (b) the arrogance to not bother to pick up a book,
> and sometimes (like our alt.2600 visitor) enough arrogance
> to assume that their first attempt is a world-beater;
> (c) the lack of some general common sense about the speed of
> computers---what's "slow," what's "fast," what's a "large number";
> and (d) the ethical numbness to put the technology in something
> human beings will use.
Maybe it's just me, but somehow "Marilyn Monroe encryption" has a nice
ring to it -- that perfect combination of ignorance and just enough
intelligence to be REALLY dangerous.
--
Later,
Jerry.
The universe is a figment of its own imagination.
------------------------------
From: Jeff Williams <[EMAIL PROTECTED]>
Subject: Re: More idiot "security problems"
Date: Fri, 17 Dec 1999 10:59:35 -0600
==============0872B5C2B01FF9A7BFA9054E
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Convenience does seem to be more important to Joe Average than security.
Perhaps we need to modify the system from the ground up, so that security is
not only built in, but transparent (or as close to transparent as possible). Those
aspects which cannot be transparent need to be arranged such that they cannot
be disabled or bypassed.
Yeah, I know that this means both new hardware and OS designs (and probably
new applications), but I cannot imagine missing the current PC hardware design,
nor the current dominant OS.
Jeff
Xcott Craver wrote:
> Trevor Jackson, III <[EMAIL PROTECTED]> wrote:
> >
> >There is no reason to expect crypto to be better than average in algorithm
> >research. There are lots of reasons to expect crypto to be worse than
> >average. Chief among these is the fact that the author is unable to tell,
> >without great effort, when he has failed.
>
> >But encryption is almost the exact opposite of sort(). The removal of order
> >rather then the imposition thereof. So the average coder can't
> >tell a good output from a bad one. Even an expert cryptologist requires
> >an effort to distinguish the really bad from the merely fatally flawed.
> >
> >The effect of these conditions is so predictable it ought to have a name like
> >"<Someone>'s Law of Cryptology"
>
> Bruce Schneier and Counterpane have been known to assert, in
> talks and white papers, that good crypto/security cannot be
> distinguished from bad crypto/security. I've always considered
> this "Schneier's first law."
>
> His second law being a remark he made at HOPE-II, which, in context,
> referred to the tendency of people to simply disable annoying or
> restrictive security measures: "The user will pick dancing pigs
> over security every time."
>
> -Scott
--
Jeff Williams - Alcatel USA.
Did you know that there is enough sand
in North Africa to cover the entire
Sahara desert?
==============0872B5C2B01FF9A7BFA9054E
Content-Type: text/html; charset=us-ascii
Content-Transfer-Encoding: 7bit
<!doctype html public "-//w3c//dtd html 4.0 transitional//en">
<html>
Convenience does seem to be more important to Joe Average than security.
<br>Perhaps we need to modify the system from the ground up, so that security
is
<br>not only built in, but transparent (or as close to transparent as possible).
Those
<br>aspects which cannot be transparent need to be arranged such that they
cannot
<br>be disabled or bypassed.
<p>Yeah, I know that this means both new hardware and OS designs (and probably
<br>new applications), but I cannot imagine missing the current PC hardware
design,
<br>nor the current dominant OS.
<p>Jeff
<p>Xcott Craver wrote:
<blockquote TYPE=CITE>Trevor Jackson, III <[EMAIL PROTECTED]> wrote:
<br>>
<br>>There is no reason to expect crypto to be better than average in algorithm
<br>>research. There are lots of reasons to expect crypto to be worse
than
<br>>average. Chief among these is the fact that the author is unable to
tell,
<br>>without great effort, when he has failed.
<p>>But encryption is almost the exact opposite of sort(). The removal
of order
<br>>rather then the imposition thereof. So the average coder can't
<br>>tell a good output from a bad one. Even an expert cryptologist
requires
<br>>an effort to distinguish the really bad from the merely fatally flawed.
<br>>
<br>>The effect of these conditions is so predictable it ought to have
a name like
<br>>"<Someone>'s Law of Cryptology"
<p> Bruce Schneier and Counterpane
have been known to assert, in
<br> talks and white papers,
that good crypto/security cannot be
<br> distinguished from bad
crypto/security.
I've always considered
<br> this "Schneier's first law."
<p> His second law being a remark
he made at HOPE-II, which, in context,
<br> referred to the tendency
of people to simply disable annoying or
<br> restrictive security measures:
"The user will pick dancing pigs
<br> over security every time."
<p>
-Scott</blockquote>
<pre>--
Jeff Williams - Alcatel USA.
Did you know that there is enough sand
in North Africa to cover the entire
Sahara desert?</pre>
</html>
==============0872B5C2B01FF9A7BFA9054E==
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Breaking a cipher.
Date: Fri, 17 Dec 1999 17:06:12 GMT
In article <01bf488c$5a2ec8a0$1c488bca@pc001>,
"jim" <[EMAIL PROTECTED]> wrote:
> I'm only a newbie to the world of cryptography and I was wodering
about
> breaking a cipher. Is it a hard task, or is it just reversing the
cipher
> and using as many keys as possible?
A cipher is said to be broken when it no longers works as claimed.
This can be because of a short key (40 bit keys for example) or because
of some statistical/algebraic bias in the algorithm.
RC5 was [for example] broken with differential analysis, but requires
2^53 blocks [that's 2^56 bytes or 2^36 MB of data] of data and is
hardly pratical. So is the cipher insecure? Not really.
My point being, a broken cipher is not always insecure.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: First step in finding primes
Date: Fri, 17 Dec 1999 17:11:31 GMT
In AC he suggests dividing by primes upto 256 which would give you
1.12/lnx or ~79.8% of all odd composites. I was thinking wouldn't it
be easier just to check gcd(n, x) = 1, where n = 2 * 3 * 5 ... * phi
(256) [phi(x) is the x th prime]. The number would be huge at first,
but after the first few itterations would get smaller. It would save
space and probably time as well.
Just a thought.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Troed)
Subject: Re: The Cracking of SecurityPlus! 4.32
Reply-To: [EMAIL PROTECTED]
Date: Fri, 17 Dec 1999 17:20:26 GMT
Paul Crowley <[EMAIL PROTECTED]> wrote:
>There's always brute force - you know the kinds of passwords you tend
>to choose, so how hard do you think it could be to write a brute force
>cracker for them?
I know, but although I'm a Software Engineer I'm not doing any work
whatsoever on Windows - which means it would take me ages to write a
brute-force interface for Kremlin :)
If anyone's already done it, I'd be very interesed in a copy. I
remember all but 4 characters of the password ... and their positions
;)
___/
_/
Nazister, rasister och andra d�rar - ger bara sig sj�lva kalla k�rar
------------------------------
From: [EMAIL PROTECTED] (Jerry Coffin)
Subject: Re: DES key safety
Date: Fri, 17 Dec 1999 10:22:52 -0700
In article <83der9$g92$[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
> Hi
> Is DES safe towards the key? I mean if you have the cleartext and the
> ciphertext could you derrive the key? Theory and practise is two different
> issues, so actually I'm asking two questions.
This would be what's called a known-plaintext attack, and no, it's not
of much use against DES. You can get somewhat more good if you not
only KNOW the plain-text, but get to choose what text gets encrypted,
and then get to compare the encrypted to the plain version. This,
again, isn't of a _lot_ of use against DES, though it can be a little
better than not having it.
In either case, you're NOT generally talking about something like
knowing the plain-text for one or two messages -- to do any real good,
you're talking about collecting a LOT of data.
--
Later,
Jerry.
The universe is a figment of its own imagination.
------------------------------
From: Scott Fluhrer <[EMAIL PROTECTED]>
Subject: Re: First step in finding primes
Date: Fri, 17 Dec 1999 17:37:20 GMT
In article <83dqru$jr$[EMAIL PROTECTED]>,
Tom St Denis <[EMAIL PROTECTED]> wrote:
>In AC he suggests dividing by primes upto 256 which would give you
>1.12/lnx or ~79.8% of all odd composites. I was thinking wouldn't it
>be easier just to check gcd(n, x) = 1, where n = 2 * 3 * 5 ... * phi
>(256) [phi(x) is the x th prime]. The number would be huge at first,
^^^^^^
Suggestion: pi(x) is standard, while phi(x) is established
terminology for something else entirely
>but after the first few itterations would get smaller. It would save
>space and probably time as well.
Probably not (at least time, space is not a big issue here). For one,
checking the smaller primes first gives you a decent probability of
exiting early. In other words, if you fail
gcd(n, 3)
then you don't have to check gcd(n, 5), gcd(n, 7), etc.
In addition, gcd(n, x) for small x can be computed *quite* rapidly.
[Ask me for details if you don't know how].
--
poncho
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: First step in finding primes
Date: Fri, 17 Dec 1999 17:29:42 GMT
In article <83dqru$jr$[EMAIL PROTECTED]>,
Tom St Denis <[EMAIL PROTECTED]> wrote:
> In AC he suggests dividing by primes upto 256 which would give you
> 1.12/lnx or ~79.8% of all odd composites. I was thinking wouldn't it
> be easier just to check gcd(n, x) = 1, where n = 2 * 3 * 5 ... * phi
> (256) [phi(x) is the x th prime]. The number would be huge at first,
> but after the first few itterations would get smaller. It would save
> space and probably time as well.
>
> Just a thought.
As a followup, upto 1000 you get a n value of
195903406449990834312625081982063810461239723905893682238826053289686663
163798706618519516487894823215962295591154360191491895297252152667282922
829908526490233627313924040179391420109582613936349594714837571967216722
434100671185162276611331351924888489899148921571883086798968751374395193
389039680949055497503864071060338365866606835392010116359179000399044950
65203299749542985993134669814805318474080581207891125910
Which is about 416 digits... Kinda big.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
** 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
******************************
