Cryptography-Digest Digest #715, Volume #13 Mon, 19 Feb 01 12:13:01 EST
Contents:
Re: Big Numbers in C/C++ (Paul Schlyter)
RSA on FPGA ("ajd")
Steak (again) ("Henrick Hellstr�m")
Re: "RSA vs. One-time-pad" or "the perfect enryption" ("Trevor L. Jackson, III")
Re: Fractal encryption? ("Trevor L. Jackson, III")
Re: Metallurgy and Cryptography ("Trevor L. Jackson, III")
Re: Ciphile Software: Why .EXE files so large (Richard Herring)
Re: Steganography with ASCII text files (Bram Labarque)
Is there an algorithm to sequentially enumerate all transcendental (jtnews)
Re: Is there an algorithm to sequentially enumerate all transcendental (Jan
Kristian Haugland)
Re: Is there an algorithm to sequentially enumerate all transcendental numbers?
(stanislav shalunov)
Re: Is there an algorithm to sequentially enumerate all transcendental (jtnews)
Re: Is there an algorithm to sequentially enumerate all transcendental (Jon and
Mary Frances Miller)
Re: Is there an algorithm to sequentially enumerate all transcendental numbers?
(David C. Ullrich)
Re: CipherText patent still pending (John Myre)
Re: Is there an algorithm to sequentially enumerate all transcendental numbers?
("Henrick Hellstr�m")
Question about password hashing and hash chaining ([EMAIL PROTECTED])
Re: Is there an algorithm to sequentially enumerate all transcendental numbers?
("Paul Lutus")
Euler's totient function and factoring (Stefan Katzenbeisser)
Re: Is there an algorithm to sequentially enumerate all transcendental numbers?
(stanislav shalunov)
Re: Is there an algorithm to sequentially enumerate all transcendental (jtnews)
Re: Ciphile Software: Why .EXE files so large (Richard Heathfield)
Re: Is there an algorithm to sequentially enumerate all transcendental (Richard
Heathfield)
Re: Is there an algorithm to sequentially enumerate all transcendental numbers?
("Paul Lutus")
Re: Is there an algorithm to sequentially enumerate all transcendental numbers?
("Paul Lutus")
Re: Euler's totient function and factoring ([EMAIL PROTECTED])
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Paul Schlyter)
Subject: Re: Big Numbers in C/C++
Date: 19 Feb 2001 12:17:28 +0100
In article <[EMAIL PROTECTED]>,
JCA <[EMAIL PROTECTED]> wrote:
> Dann Corbit wrote:
>
>> "JCA" <[EMAIL PROTECTED]> wrote in message
>> news:[EMAIL PROTECTED]...
>>> Paul Schlyter wrote:
>>>
>>>> In article <[EMAIL PROTECTED]>,
>>>> David Sowinski <[EMAIL PROTECTED]> wrote:
>>>>
>>>>> I prefer GMP and believe that it is faster than MIRACL.
>>>>
>>>> Did you use just the C low-level routines in MIRACL when evaulating
>>>> the speed? MIRACL also has assembly language replacements for these
>>>> for the most popular processors,
>>>
>>> So does GMP.
>>
>> MIRACL is a lot easier to use.
>
> GMP is quite easy to use. At least, I have never had any problem with it.
>
>
>> The speed might be a push, but you also have a ton of algorithms already
>> implemented.
>
> Fair enough. I was just interested in the big integer stuff. anyway.
>
>> Besides which, C++ classes are so much easier to understand.
>
> Whoa, I dispute that! I have no love for C++, I am sorry to say.
You don't have to use the C++ wrapper classes in MIRACL -- underneath
them there's a traditional C interface which you can use directly, if
you prefer so.
>> MIRACL is a lot better (for me -- YMMV).
>
> Good for you!
--
================================================================
Paul Schlyter, Swedish Amateur Astronomer's Society (SAAF)
Grev Turegatan 40, S-114 38 Stockholm, SWEDEN
e-mail: pausch at saaf dot se or paul.schlyter at ausys dot se
WWW: http://hotel04.ausys.se/pausch http://welcome.to/pausch
------------------------------
From: "ajd" <[EMAIL PROTECTED]>
Subject: RSA on FPGA
Date: Mon, 19 Feb 2001 12:40:46 -0000
Anyone ever done it? Which bits of the algorithm were implemented?
Andrew
------------------------------
From: "Henrick Hellstr�m" <[EMAIL PROTECTED]>
Subject: Steak (again)
Date: Mon, 19 Feb 2001 14:29:37 +0100
Some of you requested an updated and more thorough documentation of Steak. I
have attempted to do so, and I would be pleased if any of you could take a
look and comment on the results. I would in particular appreciate comments
about unconventional terminology (which, for some reason, tend to upset some
people), logical or computational errors, and, of course, any kind of
relevant attack on the cipher.
URL: http://www.streamsec.com/sattacks.asp
http://www.streamsec.com/diffan.asp
Have fun!
--
Henrick Hellstr�m
StreamSec HB
------------------------------
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Reply-To: don't
Subject: Re: "RSA vs. One-time-pad" or "the perfect enryption"
Date: Mon, 19 Feb 2001 14:10:47 GMT
"Douglas A. Gwyn" wrote:
> The real question is whether
> much security is gained by the irregularity. One thing we are
> sure of is that the system needs to be carefully designed so that
> the key-derived structure doesn't have weaknesses due to "resonance".
Are there any known examples of such inter-cipher conflicts that would
penetrate a PRNG whitening between layers? What if the whitening seeds
were public?
------------------------------
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Reply-To: don't
Subject: Re: Fractal encryption?
Date: Mon, 19 Feb 2001 14:19:29 GMT
Mok-Kong Shen wrote:
> Simon Johnson wrote:
> >
> > I have pondered this question myself in the past and have concluded that
> > Fractal Encryption is not a clever scheme.
> >
> > It is easy to see why, take a look at a typical fractal, say the mandelbrot
> > set, there are large areas where it is plain black. In order for a fractal
> > to be a good cipher, it would have to produce white noise really.... Stick
> > with Rijndael :)
>
> One useful idea, I believe, is to intentionally introduce
> some perturbations into chaotic systems.
One can implement this suggestion by combining a strange attractor around a
simple PRNG. The PRNG dribbles entropy into the attractor such that the
"sensitive dependence" of the attractor masks the predictability of the PRNG.
This is one of my favorite techniques for pursuing Ritter's concept of provable
practical security. Not there yet tho.
------------------------------
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Reply-To: don't
Subject: Re: Metallurgy and Cryptography
Date: Mon, 19 Feb 2001 14:33:16 GMT
David Eppstein wrote:
> In article <ryRj6.79650$[EMAIL PROTECTED]>, "Tad
> Johnson" <[EMAIL PROTECTED]> wrote:
>
> > What the heck is going on here?
>
> I think it's just an ironic coincidence.
There may be a hidden name/occupation relationship. Consider hatters.
Carrol's Mad Hatter and the phrase "mad as a hatter" derive from the
effects of the mercury used to produce felt hats. Perhaps the crypto
Names derive from ancestral occupations that had beneficial effects on the
descendants.
;-)
------------------------------
From: [EMAIL PROTECTED] (Richard Herring)
Crossposted-To: talk.politics.crypto
Subject: Re: Ciphile Software: Why .EXE files so large
Date: 19 Feb 2001 14:50:32 GMT
Reply-To: [EMAIL PROTECTED]
In article <[EMAIL PROTECTED]>, Anthony Stephen Szopa
([EMAIL PROTECTED]) wrote:
> You know, I asked Borland why they don't take the bull by the horns
> and put out their own books that teach C++ from the ground up using
> their Builder RAD compiler. I asked them if they were stupid, also.
> I told them that it must be a combination of stupidity and no guts.
> I guess they are scared of MS.
Last I heard, MS owned shares in Inprise, so that seems unlikely.
--
Richard Herring | <[EMAIL PROTECTED]>
------------------------------
From: Bram Labarque <[EMAIL PROTECTED]>
Subject: Re: Steganography with ASCII text files
Date: Mon, 19 Feb 2001 14:58:01 GMT
On Mon, 19 Feb 2001 11:10:53 +0100, Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
>
> Bram Labarque wrote:
> >
> [snip]
> > I just wanted to mention there is a program SNOW that I think fits part your
>description:
> > It uses ASCII plaintext. Maybe its technique is usable/extendable to HTMLtext or
HTMLformatting.
> > http://www.darkside.com.au/snow/index.html
>
> I have some difficulty in understanding. You seem to say
> that you first apply Huffman compression and then insert
> a number of spaces (with numbers equal to the bits --
> three in a group -- to be embedded) at the end of each
> line. How are you doing that actually? The compressed file
> is one contigeous bit sequence, without separation into
> lines. What pattern of bits do you put in for these extra
> spaces? Further, in one place you wrote that in empty lines
> a number of such space groups can be placed, separated by
> tabs, contrary to the convention of putting the extra
> spaces only at the end of lines. The whole idea is thus
> yet fairly unclear to me. Do you perhaps want instead to
> insert extra spaces at the end of each line BEFORE doing
> compression? Thanks.
>
> M. K. Shen
I don't know how it works. It's not my program. I just read his webpage and thought it
might be a
usefull link (also text-based steganography). The web-page refers to the author
(Matthew Kwan)
and his firm.
Greetings Bram
------------------------------
Date: Mon, 19 Feb 2001 10:10:54 -0500
From: jtnews <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Is there an algorithm to sequentially enumerate all transcendental
Is there an algorithm to sequentially enumerate
all possible transcendental numbers?
I want to be able to generate very long
passphrases but at the same time be able
to express them succinctly in the form of mathematical
expressions.
------------------------------
From: Jan Kristian Haugland <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: Is there an algorithm to sequentially enumerate all transcendental
Date: Mon, 19 Feb 2001 16:26:43 +0100
jtnews wrote:
> Is there an algorithm to sequentially enumerate
> all possible transcendental numbers?
No.
--
Jan Kristian Haugland
http://home.hia.no/~jkhaug00
------------------------------
From: stanislav shalunov <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: Is there an algorithm to sequentially enumerate all transcendental
numbers?
Date: 19 Feb 2001 10:32:19 -0500
jtnews <[EMAIL PROTECTED]> writes:
> Is there an algorithm to sequentially enumerate all possible
> transcendental numbers?
No. There are 2^{\aleph_0} transcendental numbers.
--
Stanislav Shalunov http://www.internet2.edu/~shalunov/
Most people can do nothing at all well. -- G. H. Hardy
------------------------------
Date: Mon, 19 Feb 2001 10:32:46 -0500
From: jtnews <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: Is there an algorithm to sequentially enumerate all transcendental
Jan Kristian Haugland wrote:
>
> jtnews wrote:
>
> > Is there an algorithm to sequentially enumerate
> > all possible transcendental numbers?
Thanks for the quick response!
Is there some reference anyone can give
where I can find mathematical proof of this?
------------------------------
From: Jon and Mary Frances Miller <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: Is there an algorithm to sequentially enumerate all transcendental
Date: Mon, 19 Feb 2001 15:37:59 GMT
jtnews wrote:
> Is there some reference anyone can give where I can find mathematical
> proof of this?
Do a web search on "Cantor Diagonalization".
Technically, this is about all the reals. Since the reals is the sum of
the algebraics and the transcendentals, you probably ought to prove that
the algebraic numbers are denumerable.
Jon Miller
------------------------------
From: [EMAIL PROTECTED] (David C. Ullrich)
Crossposted-To: sci.math
Subject: Re: Is there an algorithm to sequentially enumerate all transcendental
numbers?
Date: Mon, 19 Feb 2001 16:02:49 GMT
Reply-To: [EMAIL PROTECTED]
On Mon, 19 Feb 2001 10:32:46 -0500, jtnews <[EMAIL PROTECTED]>
wrote:
>Jan Kristian Haugland wrote:
>>
>> jtnews wrote:
>>
>> > Is there an algorithm to sequentially enumerate
>> > all possible transcendental numbers?
>
>Thanks for the quick response!
>
>Is there some reference anyone can give
>where I can find mathematical proof of this?
The proof is trivial: there are uncountably many
transcendentals.
You asked
"I want to be able to generate very long
passphrases but at the same time be able
to express them succinctly in the form of mathematical
expressions."
Why do you think that transcendental numbers
are going to be useful for this anyway?
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: CipherText patent still pending
Date: Mon, 19 Feb 2001 09:00:43 -0700
Benjamin Goldberg wrote:
<snip>
> Any cipher which runs in polynomial time can be converted to a 3SAT
> problem, where the number of terms is
> O( (keysize + blocksize) * knownplaintexts ).
The point is, merely knowing that P = NP isn't enough.
If the way we know is an actual polynomial time algorithm
for 3SAT, then you could do as you say, and solve (current)
ciphers that way. More likely, the method for doing 3SAT
would lead towards more specific cipher breaking methods.
But! It is entirely conceivable that proving P = NP would
be non-constructive; for instance, by showing P != NP leads
to a contradiction, in a very abstract way. Such a proof
would give us nothing in the way of breaking ciphers.
Actually, even a general "polynomial time" algorithm isn't
necessarily the death knell of even 128-bit symmetric keys.
Suppose the algorithm is O(N^100)? (That's even longer than
2^N, for N=128.)
<snip>
> I was merely objecting to your [sarcastic?] statement
> that the scientific community "knows" that it is one or the other.
I didn't read it that way. The post said "so far as we
know". It is most reasonable to take this the same way
that he elaborated it later: "so far as we know it could
be". That is, "for all *we* know, ...".
JM
------------------------------
From: "Henrick Hellstr�m" <[EMAIL PROTECTED]>
Subject: Re: Is there an algorithm to sequentially enumerate all transcendental
numbers?
Date: Mon, 19 Feb 2001 17:06:53 +0100
Theoretically, you could assign a unique ordinal value to each
transcendental number, but you would have to use ordinal values without
predecessors (omega, 2*omega, ... , etc) so you cannot enumerate the set of
transcendental numbers. (Obs. the important distinction between assigning
ordinal values to set elements and enumerating set elements. The terminology
might differ between text books.)
--
Henrick Hellstr�m
StreamSec HB
"stanislav shalunov" <[EMAIL PROTECTED]> skrev i meddelandet
news:[EMAIL PROTECTED]...
> jtnews <[EMAIL PROTECTED]> writes:
>
> > Is there an algorithm to sequentially enumerate all possible
> > transcendental numbers?
>
> No. There are 2^{\aleph_0} transcendental numbers.
>
> --
> Stanislav Shalunov http://www.internet2.edu/~shalunov/
>
> Most people can do nothing at all well. -- G. H. Hardy
------------------------------
From: [EMAIL PROTECTED]
Subject: Question about password hashing and hash chaining
Date: 19 Feb 2001 16:14:39 GMT
Hello!
I've got some basic questions about hashing and hash&cipher chaining:
(1) What is the correct way to get from the user-entered passphrase (a) to
the
input that a symmetric crypto algorithm like Blowfish expects (b)? Is it
enough to just hash (a) with SHA1 for example?
(2) Which one, in your opinion, is more secure: SHA1 or MD5?
(3) When the crypto algorithm needs more input than the hash function
supplies, which is the correct way to chain hash results? Should I re-hash
part of the first result or the whole result? Should I append to the left or
to the right?
(4) I've once read (can't remember where) that cipher chaining does not
provide significantly more security. This doesn't seem very logical to me:
Suppose there's a specific unknown attack or weakness of algorithm A
*exclusive-or* B, then I can minimize the risk by cipher-chaining A and B,
can't I? Is there any reason why I shouldn't cipher-chain as many algorithms
as the speed of my implementation allows?
(5) As a test for the correct passphrase, would this suffice: Create a hash
of
the ciphertext, encrypt the hash and store it. To test, create the hash of
the ciphertext, decrypt the stored hash and compare the results...?
I appreciate any comments and suggestions.
Best regards,
Erich
----- Posted via NewsOne.Net: Free (anonymous) Usenet News via the Web -----
http://newsone.net/ -- Free reading and anonymous posting to 60,000+ groups
NewsOne.Net prohibits users from posting spam. If this or other posts
made through NewsOne.Net violate posting guidelines, email [EMAIL PROTECTED]
------------------------------
From: "Paul Lutus" <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: Is there an algorithm to sequentially enumerate all transcendental
numbers?
Date: Mon, 19 Feb 2001 08:21:13 -0800
"jtnews" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Is there an algorithm to sequentially enumerate
> all possible transcendental numbers?
No, because the set of transcendentals is an infinite set. Therefore "all
possible" means an uncountable set.
If you had said "enumerate a whole bunch of transcendentals," different
answer.
--
Paul Lutus
www.arachnoid.com
------------------------------
From: Stefan Katzenbeisser <[EMAIL PROTECTED]>
Crossposted-To: comp.theory
Subject: Euler's totient function and factoring
Date: Mon, 19 Feb 2001 17:30:05 +0100
It is well-known that given any positive integer n and the value of
\phi(n), where \phi is Euler's totient function, the prime factorization
of n can be computed in random polynomial time (i.e. computing \phi(n)
and factoring n are computationally equivalent).
This result is e.g. stated in Motvani&Raghavan's book on randomized
algorithms as exercise 14.3. However, I was unable to find a proof
for this fact (except for the trivial case where n is the product of
two primes, of course). Does anyone know a paper or book where I can
look up the proof and similar results (as far as I know it should be
sufficient to know any multiple of \lamda(n), where \lambda is
Carmichael's function, instead of \phi(n))?
Thanks,
--S
--
====================================================================
[EMAIL PROTECTED] (remove "XXX" before replying)
http://stud3.tuwien.ac.at/~e9625414
------------------------------
From: stanislav shalunov <[EMAIL PROTECTED]>
Subject: Re: Is there an algorithm to sequentially enumerate all transcendental
numbers?
Date: 19 Feb 2001 11:37:09 -0500
"Henrick Hellstr�m" <[EMAIL PROTECTED]> writes:
> Theoretically, you could assign a unique ordinal value to each
> transcendental number, but you would have to use ordinal values
> without predecessors (omega, 2*omega, ... , etc) so you cannot
> enumerate the set of transcendental numbers.
You can map transcendental numbers into ordinals with predecessors
injectively just fine.
"Enumerate", however, has a specific meaning: to present a recursive
function whose image is the set in question. For uncountable sets
there's obviously nothing of the sort by definition (of "recursive
function" and "uncountable").
--
Stanislav Shalunov http://www.internet2.edu/~shalunov/
The United States now sleeps under a Soviet moon. -- Nikita Khrushchev
------------------------------
Date: Mon, 19 Feb 2001 11:37:47 -0500
From: jtnews <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: Is there an algorithm to sequentially enumerate all transcendental
jtnews wrote:
>
> Is there an algorithm to sequentially enumerate
> all possible transcendental numbers?
>
> I want to be able to generate very long
> passphrases but at the same time be able
> to express them succinctly in the form of mathematical
> expressions.
Let me clarify what I mean by sequentially enumerate.
By sequentially enumerate I mean successively enumerate
all possible transcendental numbers starting from zero
to infinity.
It doesn't matter that the set itself is infinite.
My question is analagous to:
Is there an algorithm to sequentially enumerate all
prime numbers?
Here the answer is yes. Even though the set of all
prime numbers is infinite, there is an algorithm to
enumerate the entire set starting from zero to infinity.
------------------------------
Date: Mon, 19 Feb 2001 16:33:01 +0000
From: Richard Heathfield <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto
Subject: Re: Ciphile Software: Why .EXE files so large
Anthony Stephen Szopa wrote:
>
<snip>
> For what it's worth: If you are expert with Borland C++ Builder
> you can make yourself a million dollars by writing a book similar to
> Visual Basic 6: Environment, Programming, and Applications by the
> two authors Eliason & Malarkey.
>
> Then follow it up with an advanced text.
>
> At $50 a pop, let's see, 1,000,000/50 = 20,000 books. Then multiply
> this by at least 10 because you will at most get $10 per book
> yourself (hopefully.)
>
> So you'd just have to sell 200,000 copies.
If you are aiming for $1 million royalties, and get $10 per copy, you
have to sell 100,000 copies. Check the batteries in your calculator. :-)
A $50 cover price is unlikely to get you a $10 royalty on your first
book, by the way.
>
> If your book was as good as the one above you could do this.
Sadly, the book's quality isn't as important as its subject matter. If
you want to cover your costs, write about C++. If you want to make a
little cash besides, write about Java. If you want to make a million
pounds, write a romance or a thriller.
>
> It should be a slam dunk getting it published since there are no
> comparable books like this out there for Borland C++ Builder.
I think you have seriously overestimated sales levels for technical
books, and indeed the royalties payable on each copy sold.
That doesn't mean I wouldn't wish such a book to be written. For it to
be what you want it to be, however, it would have to be not only a
treatise on C++ Builder but also a high quality tutorial on C++. Such a
book, written properly, would run to two or even three thousand pages
and would have to retail for at least $100. It wouldn't sell terribly
well, either, IMHO. (If it's any help, I'd buy a copy!)
> Good luck. Love to buy one.
So would I. Good heavens! On this at least, we agree!
--
Richard Heathfield
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R Answers: http://users.powernet.co.uk/eton/kandr2/index.html
------------------------------
Date: Mon, 19 Feb 2001 16:35:55 +0000
From: Richard Heathfield <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: Is there an algorithm to sequentially enumerate all transcendental
Paul Lutus wrote:
>
> "jtnews" <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > Is there an algorithm to sequentially enumerate
> > all possible transcendental numbers?
>
> No, because the set of transcendentals is an infinite set. Therefore "all
> possible" means an uncountable set.
The set of integers is infinite but countable. Therefore, an infinite
set does /not/ imply an uncountable set.
I agree that the set of transcendentals is uncountably infinite. I am
questioning your logic, not your conclusion.
<snip>
--
Richard Heathfield
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R Answers: http://users.powernet.co.uk/eton/kandr2/index.html
------------------------------
From: "Paul Lutus" <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: Is there an algorithm to sequentially enumerate all transcendental
numbers?
Date: Mon, 19 Feb 2001 08:47:50 -0800
"Richard Heathfield" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Paul Lutus wrote:
> >
> > "jtnews" <[EMAIL PROTECTED]> wrote in message
> > news:[EMAIL PROTECTED]...
> > > Is there an algorithm to sequentially enumerate
> > > all possible transcendental numbers?
> >
> > No, because the set of transcendentals is an infinite set. Therefore
"all
> > possible" means an uncountable set.
>
> The set of integers is infinite but countable. Therefore, an infinite
> set does /not/ imply an uncountable set.
Yes -- thank you. As always, I happily stand corrected.
I often say "countable" when I should be saying "enumerable," which IMHO is
how you mean to refer to the integers. The set of integers is infinite,
therefore a numerical total cannot be assigned to the set, but they are
enumerable.
--
Paul Lutus
www.arachnoid.com
------------------------------
From: "Paul Lutus" <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: Is there an algorithm to sequentially enumerate all transcendental
numbers?
Date: Mon, 19 Feb 2001 16:54:19 GMT
"jtnews" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> jtnews wrote:
> >
> > Is there an algorithm to sequentially enumerate
> > all possible transcendental numbers?
> >
> > I want to be able to generate very long
> > passphrases but at the same time be able
> > to express them succinctly in the form of mathematical
> > expressions.
>
>
> Let me clarify what I mean by sequentially enumerate.
> By sequentially enumerate I mean successively enumerate
> all possible transcendental numbers starting from zero
> to infinity.
>
> It doesn't matter that the set itself is infinite.
But it does, by your own definition. If the set is infinite, then
enumerating "all possible transcendental numbers" is not an achievable goal.
> My question is analagous to:
>
> Is there an algorithm to sequentially enumerate all
> prime numbers?
>
> Here the answer is yes.
NO, the answer is "no." The problem is your use of the term "all possible
prime numbers." The set is infinite, therefore there is no way to assign a
meaning to "all."
When you speak of an algorithm to enumerate "all possible" members of a set,
the implication is that the algorithm will create the list and stop. If the
set is infinite, this is not possible.
I think the problem is in how you are describing the problem, not the
problem itself. You want to list an arbitrarily large number of
transcendental numbers, not "all possible."
--
Paul Lutus
www.arachnoid.com
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Euler's totient function and factoring
Crossposted-To: comp.theory
Date: 19 Feb 2001 11:57:39 -0500
In sci.crypt Stefan Katzenbeisser <[EMAIL PROTECTED]> wrote:
> It is well-known that given any positive integer n and the value of
> \phi(n), where \phi is Euler's totient function, the prime factorization
> of n can be computed in random polynomial time (i.e. computing \phi(n)
> and factoring n are computationally equivalent).
All one needs is any workable (i.e. not so large that one cannot
work with it) multiple of the (multiplicative) orders of all the
elements in Z'_n, the multiplicative group of the integers
(relatively prime to n) under multiplication.
Suppose one has such, call it k (any multiple of Carmichael's function
such as the Euler Totient, or any multiple of THAT suffices).
Write k=2^a*b were b is odd.
Then x^k=1 mod n for any x relatively prime to n.
Pick an x (random):
Calculate GCD(x,n). If that is not 1 you already have
a factor of n (you just happened to guess a factor of n).
This is NOT likely to occur ([grin]).
So ... GCD(x,n)=1 (or else you already have a factor of n).
Not calculate X=x^b mod n.
Now you have X with X^(2^a)=1 mod n.
If X=+/-1 mod n, pick another x and try again.
Now successively square X.
Consider X mod n.
Replace X with X^2 mod n
Replace X with X^2 mod n
Replace X with X^2 mod n.
etc.
EVENTUALLY you get a result which is 1 mod n
(in at most "a" steps).
Look at the X value (after successive squarings)
RIGHT BEFORE YOU GOT 1 mod n.
That is not 1 mod n (since this is the value before
you get 1 mod n).
If this is -1 mod n, pick another x and try again.
So ... hopefully you find an X (NOT congruent to 1
or -1 mod n) with X^2=1 mod n.
This is:
(X-1)(X+1)=0 mod n
BUT X-1 <>0 mod n and X+1 <>0 mod n.
So (X-1) must have SOME (but not all) the factors
of n and so must X+1.
Thus, GCD(X-1,n) will give a proper factor of n.
What is the probability that you can find an x that
works? High (unless n just happens to be a power of
a prime ... so ... check that n is NOT a power of a
prime first ... that is easy enough ... just check
that n<>2^a, n<>3^a, etc. The largest prime you
have to check is ln(n)/ln(2)).
(one would have to look at the factorization of n
to see the components of the multiplicative group
mod n to determine the actual percentage of x's
which will result in factoring n, but it is large)
Once you have one factor of n, n=AB, just do it again
for the components to factor them, etc. (n has at most
ln(n)/ln(2) factors) to get the final factorization.
The trick here is to find X with X^2=1 mod n
((X-1)(X+1)=0 mod n) but X<>+/-1 mod n.
Then GCD(X-1,n) is a factor of n.
If you have a multiple of all the multiplicative orders
(any multiple of Carmichael's function), splitting that
into an odd part and a power of two (2^a*b), taking any x,
taking X=x^b mod n and successively squaring X will very
often (so you only will have to do this for a few x's
until you have "success") lead to such an X which allows
you to factor n.
------------------------------
** 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 by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
