<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Fri, Aug 14, 2015 at 11:11 AM, Richard Outerbridge <span dir="ltr"><<a href="mailto:outer@sympatico.ca" target="_blank">outer@sympatico.ca</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span><br>
> On 2015-08-14 (226), at 12:35:09, Bill Cox <<a href="mailto:waywardgeek@gmail.com" target="_blank">waywardgeek@gmail.com</a>> wrote:<br>
><br>
> Duh... any operator of the form Finv(F(a) + F(b)) forms a group.  It is associative and commutative.  The identity element is Finv(0).  The inverse of x is Finv(-F(x)).  I really would have enjoyed the class where they teach this :)<br>
<br>
</span>Somewhat sarcastic are we feeling this morning, Sir?  Usual shave?<br>
__outer<br>
<br>
</blockquote></div><br></div><div class="gmail_extra">Actually, there's a sad story here.  I love group theory.  However, in the class I took at Berkeley on intro group theory, they allowed a prof who had recently had a stroke teach it, but the guy had lost all of his mathematical ability.  So... we all failed the final, and the math department gave us all A's anyway.  I was unable to continue with the second course since I had learned nothing from the first.  So, all I have now is a Wikipedia level of knowledge of group theory.</div><div class="gmail_extra"><br></div><div class="gmail_extra">Anyway, I had fun this morning coming up with all sorts of group addition laws of the form Finv(F(a) + F(b)).  Here's one of the simplest:</div><div class="gmail_extra"><br></div><div class="gmail_extra"><div class="gmail_extra">  let F(x) = 1/x for x != 0, and 0 for x = 0<br></div><div class="gmail_extra">  Finv(x)  = 1/x for x != 0, and 0 for x = 0</div><div class="gmail_extra">  Addition rule: 1/(1/a + 1/b), or 0 if a == 0, b == 0, or 1/a + 1/b == 0</div><div class="gmail_extra"><br></div><div class="gmail_extra">We need a "0" element, which is why we need F(0) = 0.  Now check for inverse:</div><div class="gmail_extra"><br></div><div class="gmail_extra">  inv(a) = Finv(-F(a)) = 1/(-1/a) = -a</div><div class="gmail_extra"><br></div><div class="gmail_extra">We can define this on the open interval (-1, 1), which excludes 1, and -1, which map to themselves, which would cause problems.  This seems to satisfy the definition of a group.</div><div class="gmail_extra"><br></div><div class="gmail_extra">To make it faster for modular arithmetic, we only have to do the modular inverse at end of computation if we track numerator/denominator separately:</div><div class="gmail_extra"><br></div><div class="gmail_extra">an/ad @ bn/bd = 1/(ad/an + bd/bn) = 1/((ad*bn + an*bd)/(an*bn) = an*bn/(ad*bn + an*bd)</div><div><br></div><div>This is only 3 multiplications and one addition per group operation, which I think is quite a bit faster than Edwards curve performance with protective coords.  Have simpler groups like this one been broken?  I'm trying to get my head around why we need the full complexity of elliptic curve crypto to get the security we need, and understanding weaknesses in this system and why such weaknesses are not in regular elliptic crypto would give me some more confidence in elliptic crypto.</div><div><br></div><div>I wrote some simple Python code to implement it, which is attached.  An interesting property in this group is that anything multiplied (not added) by itself is 1.  One way to think of it is that the group operation is putting n resistors in parallel, and the result is the resistance of the parallel structure.  Are there standard attacks I can try against it?</div><div><br></div><div>Bill</div></div></div>