Request for Comments [suggestions, queries, etc] w.r.t LibTomMath
Tom St Denis
almost have the 100$ required to release the new ch1] and over the past
few LTM releases [notably 0.22, 0.23 and what will be 0.24] more than a
few algorithms have been improved.
Right now I'm still editing ch1 [moving to ch2 early this week] so I'm
not into the core math yet.
This is why I'm asking if there are any request for features, updates,
bug fixes, etc to the code base before I get into the heavy chapters.
Barring any massive bug fix or optimization when I edit a chapter the
algorithms in it, they will be finalized [with the exception of minor
typos and such] as I don't want to continually update algorithms while
editing the English.
So if you have anything to share please reply to this thread [or reply
in private] so I can take it under consideration immediately.
Some relevant URLs
LibTomMath
http://math.libtomcrypt.org
The Book
http://book.libtomcrypt.org
For those attending CRYPTO'03 I will be bringing a few full printouts to
show off [possibly let certain people keep copies]. The book is rather
"big" so I will only be bringing seven copies of the text.
Tom
Marcel Martin
> ...
> This is why I'm asking if there are any request for features, updates,
> bug fixes, etc to the code base before I get into the heavy chapters.
> ...
Why did you write your GCD so that it returns 1 when both arguments
are 0? It is clear that you did it intentionally, but why?
Mathematically GCD(0,0) is not defined but computationally the result
must be 0:
1) 0 can only be returned with GCD(0,0), no ambiguity.
2) Suppose one of your users wants to compute the GCD of 3 values
(x,y,z). This user will call twice the gcd routine.
d := gcd(x,y);
e := gcd(d,z);
Now suppose (x,y,z) = (0,0,65). With your library the result will be
1 whereas the right result is 65.
Marcel Martin
Tom St Denis
> Tom St Denis a écrit :
>
>
>>...
>>This is why I'm asking if there are any request for features, updates,
>>bug fixes, etc to the code base before I get into the heavy chapters.
>>...
>
>
> Why did you write your GCD so that it returns 1 when both arguments
> are 0? It is clear that you did it intentionally, but why?
It made sense at the time.
> Mathematically GCD(0,0) is not defined but computationally the result
> must be 0:
> 1) 0 can only be returned with GCD(0,0), no ambiguity.
Technically 0 does not divide 0 though [1 does].
> 2) Suppose one of your users wants to compute the GCD of 3 values
> (x,y,z). This user will call twice the gcd routine.
> d := gcd(x,y);
> e := gcd(d,z);
> Now suppose (x,y,z) = (0,0,65). With your library the result will be
> 1 whereas the right result is 65.
This makes sense. I'll make the change.
Tom
Colin Andrew Percival
> Technically 0 does not divide 0 though [1 does].
0*1=0. Therefore, there exists an x in Z such that 0*x=0. By definition,
this means that 0 divides 0.
Realize that the word "greatest" in "GCD" is with respect to the partial
ordering imposed by divisibility, not with respect to normal integer
comparison; this has the unfortunate consequence of making the GCD
non-unique (gcd(6,9)={3,-3}) and sometimes non-existent (for example, in
some polynomial rings over algebraic number fields), but puts it on much
more firm mathematical ground.
Colin Percival
Marcel Martin
> > Why did you write your GCD so that it returns 1 when both arguments
> > are 0? It is clear that you did it intentionally, but why?
>
> It made sense at the time.
>
Do you intend to answer this way if ever someone, at CRYPTO, asks you
a question regarding a problem with your library?
> > Mathematically GCD(0,0) is not defined but computationally the result
> > must be 0:
> > 1) 0 can only be returned with GCD(0,0), no ambiguity.
>
> Technically 0 does not divide 0 though [1 does].
Does it 'technically' exist a couple (x,y) such that 0x + 0y = 1?
Moreover, here, one has not to be mathematically correct (since,
mathematically, GCD(0,0) is not defined). All one has to do is to
raise an exception or to return a special value signaling the
problem. Returning 0 is the best way of doing it.
Marcel Martin
Mark Wooding
> Does it 'technically' exist a couple (x,y) such that 0x + 0y = 1?
> Moreover, here, one has not to be mathematically correct (since,
> mathematically, GCD(0,0) is not defined).
I don't see why not. My recollection is that the GCD of x and y is the
integer g such that (a) g|x and g|y, and (b), for all f where f|x and
f|y, we have f|g. We have uniqueness obviously if g != 0 (since we'd
have g p = g' and g' q = g for integers p and q, so g = g p q => p = q =
1 => g = g'). Obviously n|0 for all integers n. We can show that
gcd(0, n) = n for any n != 0 -- this is trivial. Finally, gcd(0, 0) = 0
by the definition, but we must also show uniqueness: let n be a GCD of
(0, 0): pick any other integer x, then x|0, so we must have x|n; but if
n != 0 and |x| > |n| this is impossible, so we conclude n = 0. Thus,
the definition is good for all pairs of integers.
(Wow, that ended up being denser than I'd expected.)
-- [mdw]
Tom St Denis
> Tom St Denis a écrit :
>
>>Marcel Martin wrote:
>>
>>>Why did you write your GCD so that it returns 1 when both arguments
>>>are 0? It is clear that you did it intentionally, but why?
>>
>>It made sense at the time.
>>
>
>
> Do you intend to answer this way if ever someone, at CRYPTO, asks you
> a question regarding a problem with your library?
Let me break it down for ya sparky.
I'm a high school grad, who by misfortune of having a short attention
span and lax work ethic passed with a C average. I failed to get into
university [first round, I was accepted later, long story] and
eventually wound up in vocational college. I have oodles of time on my
hands to code things that apparently a couple dozen others like.
So when I say "made sense at the time" I mean when I wrote the function
it made sense because I had just spent 12 hours working on the library
[not to mention 16 hours the previous two weeks] and wrote it that way.
Recall I wrote the core of LibTomMath over the course of a few weeks
during my x-mas break [dec 2002]
I didn't say I was right nor was I arguing I was right. I said "it made
sense at the time".
>>>Mathematically GCD(0,0) is not defined but computationally the result
>>>must be 0:
>>>1) 0 can only be returned with GCD(0,0), no ambiguity.
>>
>>Technically 0 does not divide 0 though [1 does].
>
>
> Does it 'technically' exist a couple (x,y) such that 0x + 0y = 1?
> Moreover, here, one has not to be mathematically correct (since,
> mathematically, GCD(0,0) is not defined). All one has to do is to
> raise an exception or to return a special value signaling the
> problem. Returning 0 is the best way of doing it.
I do that now [mp_zero(c)].
Tom
Tom St Denis
x|y means divisible by y right?
So what exactly does x|0 mean?
Tom
Mark Wooding
> x|y means divisible by y right?
<sigh> No, it means x divides y, i.e., there exists an integer k such
that x k = y.
> So what exactly does x|0 mean?
It means that there's an integer k such that x k = 0. Take, for example
k = 0.
-- [mdw]
Tom St Denis
> Tom St Denis <tomst...@iahu.ca> wrote:
>
>
>>x|y means divisible by y right?
>
>
> <sigh> No, it means x divides y, i.e., there exists an integer k such
> that x k = y.
Yeah, oops. Brain fried!
>>So what exactly does x|0 mean?
>
>
> It means that there's an integer k such that x k = 0. Take, for example
> k = 0.
Makes sense. Anyways I modded my gcd such that gcd(0,0)=0
Tom