Re: Fermat's primality test vs. Miller-Rabin
I guess the small increase in efficiency would not be worth additional
program code.
That depends on the size of the numbers you're working with...
Considering the research that goes into fast implementations of
PowerMod I don't think the required computation is trivial.
Although the Carmichael numbers fool the Fermat test
(that is, $a^{n-1} = 1 (n)$) for *all* a, there are no such things for
the Miller-Rabin test: for any odd composite n at least 3/4 of a's
fail the test, that is if you made m MR tests with random a's then you
are mistaken with probability at most (1/4)^m.
Yes I guess the difference is that with MR you are trying to find a
number that is *likely* a prime, whereas with Fermat you are testing
primality. But MR will still fail when given a Carmichael number,
since elsewhere MR is defined as iterated application of the Fermat
test [1].
[1] http://www.nist.gov/dads/HTML/millerRabin.html
--
Jeremiah Rogers
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Fermat's primality test vs. Miller-Rabin
It appears that Fermat's test can be fooled by Carmichael numbers, whereas Miller-Rabin is immune, but I'm not sure why. Where does it say Miller-Rabin is immune to Carmichael numbers? It seems confusingly worded and says that Fermat's Test is not immune to Carmichaels, but this does not imply M-R is immune. Additionally, the book says We limit the probability of a false result [with M-R] to 2^(-128) to achieve our required security level. It appears that M-R tests that just before the squaring of a that produces a residue of 1, is the residue n-1. Apparently that's not true for most bases of Carmichael numbers. Is that the distinction that makes Miller-Rabin a stronger primality test? To me it looks like M-R just eliminates some needless computation that a naive application of the Fermat test would require. Computing a^n - a (mod n) is harder than computing smaller powers of a and checking each of those. This is why s the largest s such that 2 does not divide s is found. If one power q is such that a^(sq) - a != 0 (mod n) then continued squaring isn't going to generate a power of a that is congruent to 1. The n vs n-1 distinction appears only when discussing if x^2 - 1 = 0 (mod n). This is why M-R fails for n=2. -- Jeremiah Rogers - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Java: Helping the world build bigger idiots
It used to be that checking bounds on certain collections was less
efficient than waiting for the out of bounds exception. I think Joshua
Bloch discusses this in his book.
I've also seen this in generated code where you aren't sure of the
nature of the object you're indexing and thus don't know the
appropriate length variable (.length vs .length()).
That said it's still awful.
On 9/19/05, Peter Gutmann [EMAIL PROTECTED] wrote:
Found on the Daily WTF, http://www.thedailywtf.com/forums/43223/ShowPost.aspx:
try {
int idx = 0;
while (true) {
displayProductInfo(prodnums[idx]);
idx++;
}
}
catch (IndexOutOfBoundException ex) {
// nil
}
The editor also comments that when he got the first few of these submitted he
rejected them as being faked, but ended up with so many that he realised this
usage must be relatively common.
Peter.
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
--
Jeremiah Rogers
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Feature or Flaw?
This site is set so that there is a frame of https://www.bankone.com inside my https://slam.securescience.com/threats/mixed.html site. The imaginative part is that you may have to reverse the rolls to understand the impact of this (https://www.bankone.com with https://slam.securescience.com frame - done via cross-user attacks trivially). Let me get this right: here we have a page which appears to be from domain A, but in fact it has frame(s) which display domain B. This allows a page to have the content from domain B but the outward appearance is of domain A, including the SSL lock on the page which indicates this page is safe to the user. It looks like this allows one to spoof domain A quite successfully, unless I'm missing something. Jeremiah - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
origin of SHA 224 initial hash values
I'm having trouble pinpointing the origin of the initial hash values for SHA 224 and, for that matter, 128. These values are defined as hex representations of cube roots of primes for sha-1 of lengths 256, 384 and 512, but I can't find where they were obtained for the shorter lengths. Thanks and apologies if this is something well known. - jeremiah - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: A-B-a-b encryption
On Nov 16, 2003, at 12:24 PM, lrk wrote: Stupid crypto, probably. Unless I'm missing something, this only works if A(A(M)) = M. Symetric crypto, not just symetric keys. NEVER willingly give the cryptanalyst the same message encrypted with the same system using two different keys. For the simple case, suppose F(X) = X ^ S (exclusive or with a string generated from the key). Then M = A(M) ^ B(M) ^ B(A(M)), right? Probably something similar for other symetric systems. This is Shamir's Three-Pass protocol and it doesn't require a symmetric system, it requires a commutative system. See Schneier p 516 (section 22.3) or [1] for details. so A(A(M)) != M Unless I'm mistaken, this commutative system does not leak information in the same way as XOR does. - Jeremiah [1] http://www.afn.org/~afn21533/keyexchg.htm - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
