Tips: use longs, if not bigints. Make modular exponentiation, etc. modular so you can easily reuse them in hwk 8.

Slides from

Sample research paper is in the same place. Yours doesn't have to look ANYTHING like it.

> in a negative. Also, the notation of the modular operation is very > confusing in the reader....when it says check if b = 1 (mod n) it is not > saying b = 1%n it is b%n =1, so in the cases where it says compute b = > a^r(mod n) and b = b^2(mod n) what exactly should we be calculating? (i.e. > where do we place the % sign ) His notation is what mathematicians use. b = 1 (mod n) is saying test if b = 1 when you are doing mod n math. b = a^r (mod n) is saying store the result of a^r into b, but you're doing mod n math. I agree it is kinda confusing (especially the first time you see it) but if you take a second look at the notation, what is implied becomes clear. Remember that this is standard notation for mathematicians; it wasn't cooked up just to confuse you.

> In your notes you state that 3 = -1 % 4 > In Java, ((-1) % 4) is -1. > Am I missing something here? Sorry I should say mod. In case I do that again, I sometimes use % to mean a "math" modulus operator where the result of performing % n is between 0 and n-1 inclusive. Neither C/C++ nor Java do this, apparently. I'll try to only use the word "mod" in the future.Yes that's right! "%n" in your programming language might not be the same as "mod n." Do tests to be sure. See also the note below, which talks about this same problem. To be honest, I'm surprised this hasn't come up before. 3 = -1 (mod 4) is correct. If 3 does not equal -1%4 in your programming language, you will have to get around it. Hint: add n to make everything positive.

> Do we only need to show the trace for the first composite number? > > Meaning, we list all the primes we find, and just show the test for that composite number? Exactly. Show what the program gives you for all your 10 test values. Note that when normally running the program, you don't always have to use all 10 test values.

> For part QS1, the sheet says to go for x = [0, 1, -1, 2, -2...r, -r] for r ~ > 400. Is that correct? It just seems excessive since all he examples are around > 10-60. It doesn't affect my output but seems like overkill. Let me know. Thank > you. Start small, and work your way up. The problem with too small of a r is that you won't get enough rows in your table from which to build sets of tau.

> What can I use for large integers in C++, I have looked all over the web and I can't find anything. http://www.google.com/custom?site=search&hl=en&lr=&ie=ISO-8859-1&safe=off&cof=&q=arbitrary+precision+library+C%2B%2B&btnG=Google+SearchYikes 3 people have asked already

> In the Miller-Rabin primality test, in the for loop, when it says if b = > -1(mod n) then return prime, else compute b^2(mod n)......what does it mean > by the compute b^2(mod n)? Is it saying that b = b^2(mod n)? Thank you for > your help. Yup. Store it back into b.

> I'm doing the first part of hw7 (the miller-rabin test) and ran into > some confusion in the algorithm... on page 8 of the > Primality and Factorization chapter in the reader steps MR3 and MR4 state > > MR3. Compute b = a^r (modulo n) > MR4. if b = 1 (modulo n), then Return("prime") and END > > -> since a, r, and n, are known step MR3 is straight forward > -> but the b = 1 (modulo n) is confusing to me.. does this mean > calculate euclidean(b,n) and check to see if the result is 1 > [and if so return prime] ?? All he means is compute b in MR3, and test if it's 1 in MR4. Since you already did mod in MR3, you don't really have to do it in MR4. The operation is still there, but you don't have to do it explicitly. > if this is so, then MR6a is even more confusing to me. how could i > get a -1 for a result from the euclidean algorithm? For example 3 = -1 modulo 4. There are infinitely many numbers that are -1 modulo n for any n. At least I think that's the case. So you won't get a negative number as a result of Euclidean, but you might get something that is -1 modulo n. Hope that makes sense. If not, discussion/OH will help.

Top | Home > CS178 > Homework 7