Hi Tim, Apologies! It's disorienting at first, and most of all when one actually tries to sit down and do a real example. The version on the slides was not written in one go, I assure you.

## Advertising

Let's go through, and see what's not working. ************************** > I'm trying a very simple example. I'm going to choose, p = 3, q = 5 and a message m = 42 Already we're in trouble. p and q are fine; but remember that the plaintext space (let's call it P(N)) is the set of all integers in Z/NZ; that is, it is all numbers m 0 <= m < N You can see already that the m you chose is not in the plaintext space. Let's pick a new m to continue with; in this case, let's choose your m, but mod 15 so that it lies in P(N). Thus, our new m going forward shall be m = 12 ************************** > I'm going to pick g = 240. I think it needs to be a multiple of N that is greater than N*N, correct? No, and this is important. g has to be an element of (Z/(N squared )Z)* of order a nonzero multiple of N. That sentence is meaningless unless you're already embedded in the mathematics, so let's go through what it means, bit by bit. g must be: 1. *an element of (Z/(N squared)Z)**: everything but the outer * on the right just means that 0 <= g < N*N; in this case that means 0 <= g < 225. The outer * on the right indicates that we only want to take a certain special kind of g: one that is what we call a *unit* mod N*N; that is, it means that we require that there exist another element 0<= h < N*N such that g*h = 1 mod N*N. In our current situation, N = p*q is a product of primes, and so N*N = p**2 * q**2, and we can easily characterize G = (Z/(N squared)Z)*: G = { 0<= g < N*N such that neither p nor q divide g}. So as long as we pick a g that does not have p or q as a factor, we're good for this condition (this also includes 0, so really all of my "0 <=" in this paragraph could have been "0 < "). Another way to characterize G is to say that it is the set of integers less than N*N that are relatively prime to N*N. 2. *of order a nonzero multiple of N*: this is a little trickier. The *order* of an element g of a finite group (which G is) is the least integer k such that g^k = 1 in G. I'm not going to prove it here, but it turns out that every element of G has finite order (that is, if g is in G, then there exists a finite non-zero k such that g^k = 1), and that it is less than or equal to the Carmichael number lambda(N*N). That takes care of what 'order' means, and, like I said, order is defined for all g in G. But! We require a special order. Specifically, we only want g in G such that the order of g is a non-zero multiple of N. We might ask whether we know that such always exists (a good question, since we require it), and we do! Here's a quick proof of existence, one tied closely to Wideskies: * Take g = 1 + N (I'm going to prove, all at once, that 1+N is in G and that it has an order that fits the bill). * Consider g**N: by the binomial theorem, (1+N)*N = 1 + N*N + other terms divisible by N*N. This number is equivalent to 1 mod N*N. QED Ok, great, such g exist, and so we can require that we use one of them. But you must be careful: you can't just choose any g in G off the street and expect it will satisfy our requirements. You chose g = 240, which (1) bigger than N*N, which isn't what we want, and (2) is divisible by N, and so even if we take 240 mod N*N, we still aren't in G, much less of the 'right order' (turns out 240, being not relatively prime to N, can never be exponentiated to 1 mod N*N). For now, let's just take the standard Wideskies g, g = 1 + N = 16. If you want to go through this with a different g, give it a shot, but make sure it's got the right kind of order. ************************** > I'll pick zeta = 21. I think it needs to be greater than N. As in point 2, no. We require zeta to be in (Z/NZ)*, which, similar to the above, means a number 0 < zeta < N such that zeta is a unit. You picked 21; if we take 21 mod N we get zeta = 6, which is not a unit (in particular it is not relatively prime to p=3). Let's pick the next number greater than 6 which is in (Z/NZ)*, which is zeta = 7. ************************** Let's see what we've got. ( (16**12)*(7**15) ) mod 225 = 208. I will leave it as an exercise to check that the decryption of 208 is in fact 12. ************************** Ok, that's all so far. If the above is still not computing (literally or metaphorically), I am available to converse one-on-one either over the phone or some other medium (face time or what have you) and only too happy to go over this more. Let me know, Walter On Mon, Sep 19, 2016 at 12:13 PM, Tim Ellison <t.p.elli...@gmail.com> wrote: > On 17/09/16 06:42, wraydulany wrote: > > [Pirk 67] - Add Slide Deck to the Website Documentation Explaining > the Mathematics of Pirk > > Argh! Walter you are driving me mad! :-) > > Thank you for putting up the slides, and I really want to grok this, but > I'm struggling to work through even the simplest of examples. > I need the kindergarten version :-( > > What am I doing wrong? I'm trying a very simple example. I'm going to > choose, > p = 3, q = 5 and a message m = 42 > > Looking at page 11 on the math_deck.pdf line by line > > line 2: > N = 15. > I'm going to pick g = 240. I think it needs to be a multiple of N > that is greater than N*N, correct? > > line 3: > I'll pick zeta = 21. I think it needs to be greater than N. > > Line 4: > (240^42 x 21^15) mod 225 = 0 > > That's suspicious. > ...and if I play with my free choices of m, g and zeta I always get zero. > > Help! > > I get the gist of the flow through the deck, but I want to work through > my own examples from top to bottom. > > Regards, > Tim >