two possible coding porjects
Mon, 04 Aug 2003 16:08:46 -0500 (CDT)

Quoting Karl Hasselström <>:
> That is, you call a function that may or may not preinvert
> your divisor depending on how big it is, how many operations
> you'll do, etc.

OK, as long as there is a provision for telling it the number
of expected operations is very very large.  Pollard Rho spends
a long time computing modular squares against an invariant
divisor that can be presumed to be largish, for example.  There
is no way to know (without already knowing the factorization)
how many times it will use the inverse.

In interactive programs it is also difficult to know in advance
how many times a divisor will be used.  If the shell notices that
some number is being used as the size of a ring it ought to be
able to cache an inverse for it without a lot of drama.

Perhaps I will just go back to doing an application-specific hack.
I will need a couple of other hacks anyway, e.g. testing the low
limbs of two numbers to see if their sum or difference might be
a square.

So, if my goal is to find the remainder a%n where a is on the
order of n^2 and n is on the order of 2^10000 would I be better
off beginning with a floating point approximation or an algebraic
inverse of n?

What if the goal is GCD(a,n)?

Yeah, I know, I need to profile it and find out.

Thanks for listening to me babble, I at least got a lot out of ir.