I am seeking different efficient programming methods (algorithms) for modular exponentiation with huge exponents, viz. 160-bit to 1024-bit integers as exponents and bases. I hope to find something a bit better than repeated squaring to handle the exponent; or at least a better way of chunking it. I will be working with DWORD and QWORD segments, so this should be an interesting hack.

Example:

1376059935759825045063891486059888763810529472911 ^
1227306356230802884842928886716272231596711085779 %
1393133130738640234978081120598228122485209166367

Imagine instead of 160 bits up to to 1024 bits for all integers in the equation, the base, exponent, and modulus.

I am not the least bit interested in using 3rd party code for this project. Please point the way to _algorithms_, not libraries or units.

--
3883@sugar.bug | sybershock.com | sci.crypt

Montgomery Schorr

Not a star wars character.

Peter Fairbrother

On 11/04/2024 14:35, SugarBug wrote:
> I am seeking different efficient programming methods (algorithms) for modular exponentiation with huge exponents, viz. 160-bit to 1024-bit integers as exponents and bases. I hope to find something a bit better than repeated squaring to handle the exponent; or at least a better way of chunking it. I will be working with DWORD and QWORD segments, so this should be an interesting hack.
>
> Example:
>
> 1376059935759825045063891486059888763810529472911 ^
> 1227306356230802884842928886716272231596711085779 %
> 1393133130738640234978081120598228122485209166367
>
> Imagine instead of 160 bits up to to 1024 bits for all integers in the equation, the base, exponent, and modulus.
>
> I am not the least bit interested in using 3rd party code for this project. Please point the way to _algorithms_, not libraries or units.
>

On Thu, 11 Apr 2024 19:18:45 +0100
Peter Fairbrother <peter@tsto.co.uk> wrote:

> Montgomery Schorr

Do you mean "Scnorr" as in CP Schnorr Signatures?

Do you mean like this:

https://scholar.google.com/scholar?hl=en&as_sdt=0%2C4&q=montgomery+exponentiation&btnG=&oq=%22Montgomery%22+expon

And this:

https://scholar.google.com/scholar?hl=en&as_sdt=0%2C4&q=schnorr+exponentiation

--
3883@sugar.bug | sybershock.com | sci.crypt

On Fri, 12 Apr 2024 16:18:57 -0500
SugarBug <3883@sugar.bug> wrote:

> On Thu, 11 Apr 2024 19:18:45 +0100
> Peter Fairbrother <peter@tsto.co.uk> wrote:
>
> > Montgomery Schorr
>
> Do you mean "Scnorr" as in CP Schnorr Signatures?
>
> Do you mean like this:
>
> https://scholar.google.com/scholar?hl=en&as_sdt=0%2C4&q=montgomery+exponentiation&btnG=&oq=%22Montgomery%22+expon
>
> And this:
>
> https://scholar.google.com/scholar?hl=en&as_sdt=0%2C4&q=schnorr+exponentiation

Currently I am looking at Montgomery and Joye ladders and division chains. I hope to find some really exotic ideas to play with. I have been playing with some simple primitives that work with small exponents, but fall apart with large powers.

--
3883@sugar.bug | sybershock.com | sci.crypt

SugarBug <3883@sugar.bug> writes:
> I am seeking different efficient programming methods (algorithms) for
> modular exponentiation with huge exponents, viz. 160-bit to 1024-bit
....
> I am not the least bit interested in using 3rd party code for this
> project. Please point the way to _algorithms_, not libraries or units.

/Prime Numbers and Computer Methods for Factorization/ - Hans Riesel
/Prime Numbers: A Computational Perspective/ - Crandall & Pomerance

Phil
--
We are no longer hunters and nomads. No longer awed and frightened, as we have
gained some understanding of the world in which we live. As such, we can cast
aside childish remnants from the dawn of our civilization.
-- NotSanguine on SoylentNews, after Eugen Weber in /The Western Tradition/