ni...@lysator.liu.se (Niels Möller) writes:
I think Newton analogues exist only when b is a power, not in general.
And the most important case is prime b.
I think it exists also for b can be factorised into prime powers...
I am not familiar with the Jebelean (or Möller!) criteria for
Torbjorn Granlund t...@gmplib.org writes:
I think it exists also for b can be factorised into prime powers...
Sure, any factorization can be used with CRT, but it's only powers which
allow newton-like hensel-lifts, as far as I'm aware.
And the most important case is when b is prime.
You
[I fixed the grammar in my self-quotations, hopefully not against some
netiqette]
We don't need to insist on keeping operands positive.
Hmm. In general, one needs to replace the largest number, to make
progres. But I guess in the case of many high bits being equal, it might
not
Torbjorn Granlund t...@gmplib.org writes:
I see the need of the following:
function
mul
gcdext
add, sub
mod (div_r_sec) is more important than general division. And modular
inverse is more important than general gcdext.
I've also seen some need for add_1/sub_1.
I started a web page on this: gmplib.org/devel/sec.html
Feel free to make changes as usual.
--
Torbjörn
___
gmp-devel mailing list
gmp-devel@gmplib.org
http://gmplib.org/mailman/listinfo/gmp-devel
Torbjorn Granlund t...@gmplib.org writes:
Hmm...can one use Newton for any a^(-1) mod b (when that exists)? (I
listed gcdext for the sake of inverses, and omitted gcd.)
I think Newton analogues exist only when b is a power, not in general.
And the most important case is prime b.
I am not
Ciao,
Il Dom, 3 Marzo 2013 5:53 pm, Torbjorn Granlund ha scritto:
ni...@lysator.liu.se (Niels Möller) writes:
__gmpn_sqr_basecase
This (and also mul_basecase) should be public. They're useful for crypto
applications where numbers are known to be of moderate size and where
low code
bodr...@mail.dm.unipi.it writes:
Uhm... Why are all this _basecase functions needed? To have them running
in predictable time (only dependent on sizes, not on actual operands)?
For mul and sqr: yes, and also to avoid memory allocation.
For gcdext: No, there the point is to have O(n) storage
