Cryptography-Digest Digest #587, Volume #10 Thu, 18 Nov 99 17:13:03 EST
Contents:
Re: Realistic view of AES (SCOTT19U.ZIP_GUY)
Simpson's Book and Quantum Entanglement ([EMAIL PROTECTED])
Re: Realistic view of AES (Jerry Coffin)
Re: more about the random number generator (William Rowden)
Re: ENCRYPTOR 4.0 by Comotex USA Inc. CRACKED !! (JPeschel)
Re: Codebook examples on Web? (John Savard)
Encrypted software, decrypted on chip (Chevrier Mathiru)
"The Code Book" challenge update (Jim Gillogly)
Re: New web page for The Cunningham Project ([EMAIL PROTECTED])
Re: Fingerprints for encryption alg. (Volker Hetzer)
Re: New Scottish Crypto System (Derek Bell)
Re: What part of 'You need the key to know' don't you people get? (Tom St Denis)
Re: Fingerprints for encryption alg. (JPeschel)
Re: New Scottish Crypto System (John Savard)
Re: Codebook examples on Web? (Jim Dunnett)
Re: weak ciphers and their usage (Tim Tyler)
Re: AES cyphers leak information like sieves (Tim Tyler)
Fractionation Help on Web Site (table of powers) (John Savard)
Re: AES cyphers leak information like sieves (Tim Tyler)
Re: MPQS factoring method : proof ot its complexity. (MENIER Clement)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Realistic view of AES
Date: Thu, 18 Nov 1999 15:31:12 GMT
In article <810ru2$k8q$[EMAIL PROTECTED]>, Tom St Denis <[EMAIL PROTECTED]> wrote:
>In article <80vkiu$1uks$[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY) wrote:
>> Tom on this you are most likely correct. But I wonder what the
>> hell will happen to the export regulations. If AES is adopted by the
>> US will it allow it to be exported? You have to ralize in my country
>> many many times the left hand of government does not know what
>> the right hand does and often there is disagreement.
>
>Last I heard export rules were slacking off in both our countries.
>Apparently they are beginning to take a hint.
>
Tom your young and wet behind the ears. Government is always talking
about helping people but it rarely does. They talk about easing the rules
when in fact they usually add more rules so I would not hold your breath.
It is a constant fight to try to get asshole politicans from directing your
life from cradle to grave.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
Scott famous encryption website NOT FOR WIMPS
http://members.xoom.com/ecil/index.htm
Scott rejected paper for the ACM
http://members.xoom.com/ecil/dspaper.htm
Scott famous Compression Page WIMPS allowed
http://members.xoom.com/ecil/compress.htm
**NOTE EMAIL address is for SPAMERS***
------------------------------
From: [EMAIL PROTECTED]
Subject: Simpson's Book and Quantum Entanglement
Date: Thu, 18 Nov 1999 15:27:40 GMT
In article <8112t7$ped$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> Are mental illnesses resultant of paradoxes ?
>
> Would Freud have loved to have been able to un[en]tangle
> the knotted threads of spatio-temporal memories and
> re-weave them into a consistent associative space-time map
> for the patient to orient themselves in ?
>
> Simpson's Paradox:
> http://curriculum.qed.qld.gov.au/kla/eda/sim_par.htm
>
> Simpson's Paradox is a statistical artifact related to
> hidden variables. Here it in terms of quantum entanglement.
>
> Given that
>
> 1) A and B are complementary
> 2) A and B are both true XOR A and B are both false
>
> then, that 1) contradicts 2) is the essence of Simpson's Paradox.
>
> We can make an arbitrary determination that "A is True"
> to resolve that paradox, but this choice is arbitrary as we could
> equally have chosen to make the determination that
> "B is True". Regardless of the choice we can then instantly
> determine the complementary variables state as "anti-correlated".
>
> Similarly, in entanglement the arbitrary measurement of
> a polarization or spin state will instantly (non-locally)
> determine the state of the anti-correlated entangled twin.
>
Here's an interesting connection between Simpson's Paradox and
Quantum theory:
Simpson's Paradox
http://www.deja.com/=dnc/getdoc.xp?AN=478827647
The Dechronization of Sam Magruder
by George Gaylord Simpson
http://www.rms.nvusd.k12.ca.us/mediacenter/books/the.htm
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Jerry Coffin)
Subject: Re: Realistic view of AES
Date: Thu, 18 Nov 1999 08:48:06 -0700
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] says...
> NIST has said there will be a winner or winners to AES contest. Not
> necessarily only one winner.
In fact, anybody interested in this question may want to visit the
NIST AES web site -- they have a white paper pointing out some of the
strengths and weaknesses of each decision, and seem _quite_ interested
in comments on this particular subject.
--
Later,
Jerry.
The universe is a figment of its own imagination.
------------------------------
From: William Rowden <[EMAIL PROTECTED]>
Subject: Re: more about the random number generator
Date: Thu, 18 Nov 1999 15:54:37 GMT
In article <[EMAIL PROTECTED]>, Anton Stiglic <[EMAIL PROTECTED]>
wrote:
> Tom St Denis wrote:
[snip]
> > Serial correlation coefficient is 0.001254 (totally uncorrelated =
> > 0.0).
>
> This looks like the test that checks the number of d-grams. Can
> someone comment?
I assumed this was a simple autocorrelation statistic for a shift of d =
1, if that's what you mean. Perhaps Scott Nelson, who has examined the
source, could verify this. If my guess is correct, the program would
probably sum the result of XOR on bits separated by some d less than 1/2
the total number of bits (maybe 1). Has anyone looked at this portion
of the code?
--
-William
SPAM filtered; damages claimed for UCE according to RCW19.86
PGP key: http://www.eskimo.com/~rowdenw/pgp/rowdenw.asc until 2000-08-01
Fingerprint: FB4B E2CD 25AF 95E5 ADBB DA28 379D 47DB 599E 0B1A
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Subject: Re: ENCRYPTOR 4.0 by Comotex USA Inc. CRACKED !!
Date: 18 Nov 1999 16:20:16 GMT
fungus [EMAIL PROTECTED] writes:
>The only one which works is brute-force. All the others
>assume some sort of knowledge about the plaintext (even
>if it's only a frequency distribution).
This is simply untrue.
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Codebook examples on Web?
Date: Thu, 18 Nov 1999 16:47:26 GMT
"Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote, in part:
>John Savard wrote:
>> ... Never use the words "one time" for any system that doesn't use
>> genuinely random numbers, ...
>All that is meant by "one-time pad" is that the keying material is
>not reused. What you have in mind is better called an "ideal" OTP.
I think the usual convention is that OTP means "ideal OTP", and only
ideal OTP: if a key is used to generate keying material for use on
separate occasions, (which is also true of the "one-time codebook"
suggestion) the term "stream cipher" is used.
This strict convention is intended to prevent the term OTP from being
used in ways that might mislead or confuse potential customers of
cryptographic products. (See, for example, the "Snake Oil FAQ".)
As it is very common for vendors of even quite insecure stream ciphers
to use the term "one-time pad" in describing their products, and many
popular reference works on cryptography have used the term "one-time
pad" to describe the ideal OTP, and have noted the absolute nature of
its security, I do not believe that changint the meaning of the term
"one-time pad" to make the former use legitimate would serve the cause
of dispelling harmful confusion and promoting understanding.
However, you _have_ inspired me to note, for the record, that there is
a (possibly quite secure) form of encryption intermediate between the
OTP and the stream cipher. The POTUS-PRIME connection between the U.S.
and Britain illustrates it.
Use a very secure stream cipher to encipher short messages; but use a
one-time-pad (or a randomly generated codebook, whose entries are
crossed off after use) to encipher the message indicator (the
initialization vector).
John Savard (don't snooze, don't snore)
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: Chevrier Mathiru <[EMAIL PROTECTED]>
Subject: Encrypted software, decrypted on chip
Date: Thu, 18 Nov 1999 17:44:22 +0100
Hello,
I'm looking for information (both theoretic and practical) about cpu
able to execute encrypted programs, e.g. when main memory cannot be
trusted.
Thank you
Mathieu
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: "The Code Book" challenge update
Date: Thu, 18 Nov 1999 18:26:13 +0000
Simon Singh's web page http://www.4thestate.co.uk/cipherchallenge/
has been updated with a couple of buttons at the bottom to add links
to reviews and to a status update. Stage 5, the Beale-like cipher,
is still unsolved, blocking everybody else from getting on the
leaderboard.
I was interested to see that another person has solved the crib-less
Enigma cipher; I now know of three people who have solved that stage.
It's interesting because without a crib none of the Bombe simulators
available on the net would work. My own Enigma attack used the method
in my Cryptologia paper -- I still have offprints, if anybody needs one.
--
Jim Gillogly
28 Blotmath S.R. 1999, 18:21
12.19.6.12.16, 4 Cib 4 Ceh, Fourth Lord of Night
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: New web page for The Cunningham Project
Date: 18 Nov 1999 17:20:03 +0000
Just when you thought it safe to go back on Usenet...
[EMAIL PROTECTED] (Francois Grieu) writes:
> Introductory info on the Cunningham Project is at
> <ftp://sable.ox.ac.uk/pub/math/cunningham/README>
> [with slightly outdated listings in the same directory]
I used to maintain that directory when I was still at Oxford.
However, I joined Microsoft Research almost two years ago and the
Oxford material hasn't been updated in almost all that time.
A rather more up to date version of the same material is now at
ftp://ftp.cam.uk.eu.microsoft.com/pub/math/cunningham/
I apologise that it isn't *fully* up to date. I've been busy on other
things, not least:
> ECMNET, where the Elliptic Curves factoring method is used
> for the same purpose (it is more efficient for small factors)
> <http://www.loria.fr/~zimmerma/records/ecmnet.html>
The master server for the ECMNET client/server interface runs on the
same physical machine as where the Cunningham material resides.
Paul
And now an obligatory message from my sponsors...
--
The opinions expressed in this message | Hanging on in quiet desperation is
are my own personal views and do not | the English way.
reflect the official views of Microsoft | The time is gone, the song is over.
Corporation. Paul Leyland, pleyland@ | Thought I'd something more to say.
------------------------------
From: Volker Hetzer <[EMAIL PROTECTED]>
Subject: Re: Fingerprints for encryption alg.
Date: Thu, 18 Nov 1999 18:34:33 +0100
crippa wrote:
>
> Hi,
>
> is it possible to construct an encryption algorithm X which
> will give the encrypted message a fingerprint? The fingerprint
> will assure any reader of the encrypted message -even a reader
> without the appropriate key- that the underlaying plaintext
> has been encrypted with the X algorithm.
>
> I doubt this is possible, but I might be misstaken?
Why not send the name of the algorithm along with the message?
If necessary, sign the message and the name together.
Greetings!
Volker
--
Hi! I'm a signature virus! Copy me into your signature file to help me spread!
------------------------------
From: Derek Bell <[EMAIL PROTECTED]>
Subject: Re: New Scottish Crypto System
Date: 18 Nov 1999 17:48:40 -0000
[EMAIL PROTECTED] wrote:
: and now you tell us that a high school girl from Scotland has followed in
: her footsteps? These Celts are up to something!
I wonder if the Scottish story is a mishearing of the first? I could be
wrong, but I haven't heard anything this side of the Atlantic.
Derek
--
Derek Bell [EMAIL PROTECTED] | Socrates would have loved
WWW: http://www.maths.tcd.ie/~dbell/index.html| usenet.
PGP: http://www.maths.tcd.ie/~dbell/key.asc | - [EMAIL PROTECTED]
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: What part of 'You need the key to know' don't you people get?
Date: Thu, 18 Nov 1999 17:59:49 GMT
In article <811236$2ija$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (SCOTT19U.ZIP_GUY) wrote
> are you a complete fool where did you get such a rediculus number.
> Are you stuoid enough to think that the number 26 is a binary number.
> You really are full of shit Mr Tom. Each wheel is a specail arrangement
> of 26 characters and don't forget the plug borad in the front of machine.
Let's do some math review for the newbie here. 26 positions per wheel
gets you 26^x = 2^128, therefore x = log26(2^128) = ~28
Sorry if this is too complex for the mastermind behind scottu ciphers...
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Subject: Re: Fingerprints for encryption alg.
Date: 18 Nov 1999 18:16:35 GMT
crippa [EMAIL PROTECTED] writes:
>is it possible to construct an encryption algorithm X which
>will give the encrypted message a fingerprint? The fingerprint
>will assure any reader of the encrypted message -even a reader
>without the appropriate key- that the underlaying plaintext
>has been encrypted with the X algorithm.
Sure it is.
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: New Scottish Crypto System
Date: Thu, 18 Nov 1999 18:48:31 GMT
Derek Bell <[EMAIL PROTECTED]> wrote, in part:
>[EMAIL PROTECTED] wrote:
>: and now you tell us that a high school girl from Scotland has followed in
>: her footsteps? These Celts are up to something!
> I wonder if the Scottish story is a mishearing of the first? I could be
>wrong, but I haven't heard anything this side of the Atlantic.
I believed it to be a mishearing, and that was why my post was worded
as it was: how _could_ anyone think that a young girl named Sarah
Flannery, from County Cork, and from the city of Blarney itself, was
Scottish? (Easily enough if one didn't hear all those details...)
John Savard (don't snooze, don't snore)
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: amadeus @0SPAM.netcomuk.co.uk (Jim Dunnett)
Subject: Re: Codebook examples on Web?
Date: Thu, 18 Nov 1999 19:10:18 GMT
Reply-To: Jim Dunnett
On Thu, 18 Nov 1999 06:52:43 GMT, "Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote:
>John Savard wrote:
>> ... Never use the words "one time" for any system that doesn't use
>> genuinely random numbers, ...
>
>All that is meant by "one-time pad" is that the keying material is
>not reused. What you have in mind is better called an "ideal" OTP.
Quite so. I't doesn't have to be very random, just unpredictable!
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: weak ciphers and their usage
Reply-To: [EMAIL PROTECTED]
Date: Thu, 18 Nov 1999 18:58:00 GMT
Johnny Bravo <[EMAIL PROTECTED]> wrote:
: (SCOTT19U.ZIP_GUY) wrote:
:>Here is something you can do with a crappy AES type of encryption with your
:>secret IV. Take a long file and encrypt it. Cut off the front third and last
:>third of the file. Know if a good cryptographer like me or better in case
:>your not good enough to handle it. Is given the middle thrid of file with
:>the cipher and key but not the IV the center third of file can be
:>recovered easily
: This is the attack you have been ranting about all this time? If
: your attacker has your key and IV and only the middle third of the
: file you are vulnerable?
This is not an attack: it's a demonstration that the information in the
file is held locally and not diffused througout the entire message.
This is a property of cyphers that aids cryptanalysis. The opponent
can usefully work from partial messages. He can identify known plaintext
sections with their appropriate section of the cyphertext, etc.
: Well hell, under your system if your attacker has the key and IV the
: first third of your file you are vulnerable. Under your own criteria
: scottXXu is a weak cipher whose only security lies in the chance that
: your attacker doesn't get the first part of your encrypted
: transmission, glad to see you finally admit your tinkertoy cipher
: isn't worth the electrons it was coded with.
You don't seem to have been following what David is saying.
Consequently, none of the above makes any sense.
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
--> X <-- Press here for static discharge.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: AES cyphers leak information like sieves
Reply-To: [EMAIL PROTECTED]
Date: Thu, 18 Nov 1999 19:15:16 GMT
Jerry Coffin <[EMAIL PROTECTED]> wrote:
: In article <80tg4o$tg6$[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
:> You will see that all you pet modes are an illusion. They do
:> not spread the information though the file. But either you
:> don't understand or are to lazy to test.
: Quite the contrary: that's a well-known feature of (for example) CBC.
: Its self-synchronizing property is well-known and useful. [...]
You *don't* think having a known relationship between bits of text and
bits of cyphertext assists analysis?
I don't understand. What is your problem with this notion?
:> Think why are they are this way. Could it be of use to the NSA.
: If you can show a practical attack due to the nature of CBC, feel free
: to do so. Right now, you're apparently of the opinion that a purely
: imaginary attack is more important than a very real error-recovery
: ability.
Jeez!
Would sprinkling 0s through the plaintext file also be OK if there was no
known-plaintext attack? What about chopping bits from the key - is that
all right too, so long as *you* don't know a method of cracking the
result? What about duplicating the message a few times before encryption?
If the cypher is secure what harm are you doing?
You /have/ to try and make things as secure as you possibly can, within
the constraints laced on you. This means making things as hard as you can
for the analyst. Letting him know that there's an almost one to one
relationship between bits of text and bits of cyphertext is not a good
start.
:> Look even PGP use a weak chaing mode with compression. Most
:> people don't have the software to recover the real file
:> if a change occurred in the middle of the compressed encrypted
:> text. So what fuckin good does this error recovery do anyone
:> who depends on PGP. It does them no fucking good it can
:> only be of use to a dedicated attacker.
: For those looking on, I'll translate this into understandable (and
: civil) English: you're just as clueless as ever...
You disagree?! You think (for example) that people do generally have the
software to recover from such a mess? Or perhaps you think that hardly
anybody uses the software in question, so it doesn't matter? Or perhaps
you think that there's no possible way knowledge that certain small
regions of cyphertext correspond with certain regions of plaintext can
help attackers? Perhaps you would like to clarify which, if any, of
these false views do you hold?
:> That is also way intelligent people should have the option
:> of using something like "wrapped PCBC" when they want
:> a far higher degree of security than the NSA 3 letter blessed
:> mods that you foolish think is safe.
: If you want to claim that one thing is more secure than the other, you
: need to quantify the security of each and then compare the two. [...]
No you do not.
Quantifying security in absolute terms is diffucult. However, seeing
(for example) that adding known plaintext before direct encryption with
a block cypher weakens the resulting system does not require this.
This case is directly analogous.
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
Now the universe will explode for your pleasure.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Fractionation Help on Web Site (table of powers)
Date: Thu, 18 Nov 1999 19:57:05 GMT
Well, I've vastly improved the usefulness of the table of powers I had
on my web site, and which I had linked to from several pages about
fractionation.
Using the HTML power of frames, you can choose any two power tables to
align next to one another and compare, to look for cases where a power
of one number is close to a power of another number.
John Savard (don't snooze, don't snore)
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: AES cyphers leak information like sieves
Reply-To: [EMAIL PROTECTED]
Date: Thu, 18 Nov 1999 19:41:01 GMT
Volker Hetzer <[EMAIL PROTECTED]> wrote:
: Tim Tyler wrote:
:> Volker Hetzer <[EMAIL PROTECTED]> wrote:
:> : SCOTT19U.ZIP_GUY wrote:
:> : The fact that in case of modifications not everything decrypts to garbage
:> : is no problem at all [...]
:>
:> If modifications were to reduce the message to garbage, that might
:> easily be a problem in some circumstances.
:
: In some perhaps. But it doesn't change the security.
I would say that (at least in the case of CBC mode chaining) it does
change the security. The failure to distribute the information in the
plaintext throughout the cyphertext allows types of analysis which would
otherwise be impossible. For example, a partial plaintext may offer
complete knowledge about a number of blocks of cyphertext. This would
never happen if proper diffusion had taken place - unless the entire
plaintext were known.
It doesn't take much brain to see that if a known-plaintext attack
exists, failure to diffuse will weaken the resulting cypher. And who's to
say whather a known-plaintext attack on your favourite cypher exists or
not?
:> If you want to sign a message, include a message digest, or otherwise
:> verify the message is as-sent, you should virtually never include a hash
:> in the plaintext.
:> Simply, this allows an attacker to reject invalid keys.
:
: Might be relevant if keysearch is an option for the attacker.
Is relevant. No matter how large the key, you must allow for the
possibility that part of it becomes known, and defend against breaking
the remaining section. There are /many/ ways in which partial keys can
become known, from incomplete combustion to failure of memory on the part
of defectors. From analysis of the RNG generating the keys, to operator
idiocy in passord selection.
Consequently, /anything/ that allows an automated key-search is a security
hazzard.
: You were complaining about the AES candidates.
The details of my complaints now appear misguided. However, I am
not much more happy about the use of fixed-size block cyphers now
than I was ;-|
: Do you think any of your relevant enemies can do a keysearch of
: any of them?
I don't know and I don't care. My argument does not depend on full-width
searches of the keyspace. The ability to eliminate keys systematically
has more than enough other uses.
:> If you want to sign a message, by all means go ahead, but sign it
:> *outside* a layer of strong encryption.
:
: You are not proposing sending the hash in the clear, aren't you?
No - not necessarily. I said you should "sign it *outside* a layer of
strong encryption" - so that if the hash is used to break the encryption,
the rest of your message is not compromised.
If you /still/ want hide the signature for some reason (e.g. you
don't want opponents to know whether the message has been corrupted
or modified in transit), you can always encrypt it again.
I'm assuming you're using a public authentication scheme, and your
opponent can make a good guess at your identity from (say) the message
headers and origin in this, though.
: Besides, signing is different from a hash.
Signing is a special type of keyed hash - at least in cryptography anyway.
I /assume/ you're not talking about using real ink ;-)
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
Marvin wobbles, but he's already upside down.
------------------------------
From: MENIER Clement <[EMAIL PROTECTED]>
Subject: Re: MPQS factoring method : proof ot its complexity.
Date: Thu, 18 Nov 1999 21:09:08 +0100
Reply-To: [EMAIL PROTECTED]
==============44A2DFDCDEFC9E39BC5BDBF9
Content-Type: text/plain; charset=iso-8859-1
Content-Transfer-Encoding: 8bit
> Bob Silverman wrote:
> In article <[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] (MENIER Clément) wrote:
> > Hello everyone,
> >
> > I am doing research on the Quadratic Sieve factoring algorithm.
> > But up to now I have found no proof of its complexity :
> > ___________________
> > \/(1+o(1))*(ln(n)*ln(ln(n)))
> > e
> >
> > I'd like to know if someone knows a proof of it
>
> Noone does. There is no proof. The complexity function depends
> upon an unproved assumption: that integers in the range of a
> quadratic polynomial behave as 'random' integers of the same size with
> respect to their smoothness properties.
>
> >(even if it is not
> > exact) or if someone knows where I can find one.
>
> The derivation is virtually the same as that for CFRAC. You can
> find the derivation for the latter in Knuth Vol 2. Or you can
> look at the derivation for the Number Field Sieve in Lenstra's (ed)
> book.
>
Thanks a lot, I have read Knuth's derivation and it seems a little dark
but I am sure that I'll be able to find it out.
> >
> > I am also looking for some example of the o(1) constant in the
> > algorithm for different implementations and machines.
>
> What do you mean by "example"? I have (a lot of) data on the o(1) term
> for my implementation on Sparc's and on Pentium based PC's. What are
> you looking for?
What I am lookink for is datas on the o(1) on PC's and other machines. I
am trying to find it for some different implementation (first for the QS
algorithm then for the MPQS with all the different improvement). It is just
to give some real value (as it seems it can go as high as 5 for the QS but
noone seems to have any such data on the o(1)).
> 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/
> Before you buy.
==============44A2DFDCDEFC9E39BC5BDBF9
Content-Type: text/html; charset=us-ascii
Content-Transfer-Encoding: 7bit
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML>
<P>> Bob Silverman wrote:
<BR>> In article <[EMAIL PROTECTED]>,
<DL>> [EMAIL PROTECTED] (MENIER Clément) wrote:
<BR>> > Hello everyone,
<BR>> >
<BR>> > I am doing research on the Quadratic
Sieve factoring algorithm.
<BR>> > But up to now I have found no proof of its complexity :
<BR>>
>
___________________
<BR>>
>
\/(1+o(1))*(ln(n)*ln(ln(n)))
<BR>>
>
e
<BR>> >
<BR>> > I'd like to know if someone knows a proof of
it
<BR>>
<BR>> Noone does. There is no proof. The complexity function depends
<BR>> upon an unproved assumption: that integers in the range of a
<BR>> quadratic polynomial behave as 'random' integers of the same size
with
<BR>> respect to their smoothness properties.
<BR>>
<BR>> >(even if it is not
<BR>> > exact) or if someone knows where I can find one.
<BR>>
<BR>> The derivation is virtually the same as that for CFRAC. You
can
<BR>> find the derivation for the latter in Knuth Vol 2. Or you can
<BR>> look at the derivation for the Number Field Sieve in Lenstra's (ed)
<BR>> book.
<BR>>
<BR> Thanks a lot, I have read Knuth's derivation and it seems
a little dark but I am sure that I'll be able to find it out.
<BR>> >
<BR>> > I am also looking for some example of the o(1)
constant in the
<BR>> > algorithm for different implementations and machines.
<BR>>
<BR>> What do you mean by "example"? I have (a lot of) data on the
o(1) term
<BR>> for my implementation on Sparc's and on Pentium based PC's.
What are
<BR>> you looking for?
<P> What I am lookink for is datas on the o(1) on PC's and
other machines. I am trying to find it for some different implementation
(first for the QS algorithm then for the MPQS with all the different improvement).
It is just to give some real value (as it seems it can go as high as 5
for the QS but noone seems to have any such data on the o(1)).
<P>> Bob Silverman
<BR>> "You can lead a horse's ass to knowledge, but you can't make him
think"
<BR>>
<BR>> Sent via Deja.com <A HREF="http://www.deja.com/">http://www.deja.com/</A>
<BR>> Before you buy.</DL>
</HTML>
==============44A2DFDCDEFC9E39BC5BDBF9==
------------------------------
** 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
******************************
