Lurid Obsession with Mod Inverse - Page 3

ewmayer · 2012-08-04, 00:34

Ross, sorry for the brief thread-hijack, but by way of a Friday Humor respite, I'd like to point out that while you may not have anything suitable for the math literature in this thread yet, you probably have material for a half-dozen patents.

I happened to do an online search related to mod-inverse just now, and found myself appalled by the trivial garbage that has been patented in this and related areas, "because of its tremendous relevance to cryptography". Check out the following "groundbreaking methematical researshes!" which have been patented - these were just from clicking on 4 such links, of which I summarize 3:

Converting mathematical functions to power series

Quote:

What is claimed is:

1. A method comprising: obtaining from a machine readable storage medium a set of numeric values for coefficients of a power series that converges on a specified mathematical function; calculating a plurality of terms of the power series using the set of numeric values; and returning a sum of the plurality of the terms of the power series for the specified mathematical function.

Having authored several patents - though not nearly so revolutionary as the above one - I can tell you that "plurality" is pompous patent-ese for "one or more". I believe I assigned this "groundbreaking invention" as one of my freshman-level Computers In Engineering homework projects in my previous life as a college professor. Ah yes, here it is: Weekly project #2: Summation of Power Series.

Method for calculating arithmetic inverse over finite fields for use in cryptography

Impressive-sounding title, no? Someone has discovered an algorithm better than the eGCD, from the sound of it. Only ... not so much:

Quote:

A method for calculating greatest common divisors and modular inverses using the extended Jebelean GCD algorithm keeps track of the number of times that U3 and V3 have been divided by two in the process of calculating the greatest common divisor and correct the modular inverse for these divisions. The shifting of the binary values representing U3 that occurs during the calculation of the GCD is accomplished by changing the position of respective pointers to bit positions in the binary values rather than implementing a shifting operation.

A.k.a. "accumulation of a shift count".

Lastly - I'm too nauseated to delve further into this cesspit than this - JasonP and other NFS-implementers may be surprised to to find that if they have ever coded up a small-prime sieve, they may very well be violating the following revolutionary and highly non-obvious invention by several IBM researchers:

Accelerated prime sieving using architecture-optimized partial prime product table

Quote:

This embodiment teaches a variation of GCD-based sieving, building tables of prime products, but intentionally restricting the size of table entries to fit within a single machine word. This combination allows one to mix advantages of the two most popular sieves, while retaining the simple and straightforward structure of the simpler one. Divisor length restriction can provide significant savings in the number of long divisions, but may be implemented with only two very specific primitives. The two primitives offer better optimization capabilities than a fully generic multiword arithmetic library.

So, that hex-F-to-the-left-of-the-zeros? There's a patent.

Number of zeros increases each iteration? There's a patent.

3q^2 sometimes has more than 5 good bits? There's a patent.

3q can be evaluated as 3*x or - check this out, it's frickin' brilliant - as x+x+x? There's a patent.

I'm sure you can can come up with at least 2-3 more. :)

only_human · 2012-08-04, 01:57

Quote:

Originally Posted by ewmayer

I'm sure you can can come up with at least 2-3 more. :)

Anyone could. I am a regular reader of Groklaw and the patent insanity is often discussed there. I hate the current mess. It is a patent troll paradise and the tech world is increasingly entering alignments resembling cold war mutually assured destruction brinkmanship. As for all the craptastic patents out there -- it's sickening. It seems like everything that ever has been done is somehow patentable again if you throw the words "electronics" or "with a computer" at it. Taking a number to use a toilet was a patent IBM was trying for at one point. The whole system needs a big flush.

only_human · 2012-08-05, 20:03

Now the meat of the iterations.

I'm going to try to show it in very basic notation with very few words starting from the qinv value of 1.

x = 2z
q = x+1
qinv =1

any iteration:{
t = q*qinv;
qinv = qinv * (2-t)
}

a few steps through it:

iteration 1:
t = (x+1)*1 = x + 1
2-t = -x + 1
qinv = qinv_prev*(2-t) = -x + 1

Iteration 2:
t = q * qinv
= - x² + 1
2-t = x² + 1
qinv = qinv_prev*(2-t) = - x³ + x² - x + 1

Iteration 3:
2-t = x⁴ + 1
qinv = qinv_prev * (2-t) = - x⁷ + x⁶- x⁵ + x⁴ - x³ + x² - x + 1

What happens with t is all the inner terms vanish leaving only the first and last terms. In this iteration I show t in detail
Iteration 4:
t = q * qinv
= (x + 1) * qinv
= (x + 1) * (- x⁷ + x⁶- x⁵ + x⁴ - x³ + x² - x + 1)
= - x⁸ + x⁷- x⁶ + x⁵ - x⁴ + x³ - x² + x +(- x⁷ + x⁶- x⁵ + x⁴ - x³ + x² - x + 1)
= -x⁸ + 1
2-t = x⁸ + 1
qinv = (2-t) * qinv_prev = (x⁸ + 1)*(- x⁷ + x⁶- x⁵ + x⁴ - x³ + x² - x + 1)
= - x¹⁵ + x¹⁴. . . -x + 1

I've hidden a factor of two inside x for convenience. xⁿ is the same as 2ⁿzⁿ. The sign changing caused by 2-t could be simplified by using a precomputed -q instead of q when t is calculated and then just adding 2 but at best removes a single neg instruction. Sigma notation would be better but this will do for now. Looking at this offers hints to extending to multiword computations.

jasonp · 2012-08-07, 16:58

Quote:

Originally Posted by ewmayer

Lastly - I'm too nauseated to delve further into this cesspit than this - JasonP and other NFS-implementers may be surprised to to find that if they have ever coded up a small-prime sieve, they may very well be violating the following revolutionary and highly non-obvious invention by several IBM researchers:

The 'meat' of the patent describes a recursive method to pack products of as many primes as possible into the fewest fixed-size machine words as possible, and in my mind this makes the patent slightly more innovative than 'duh'.

only_human · 2012-08-10, 02:47

x=2z
q=x+1

if qinv is started with a value of 1, successive iterations of this mod inverse algorithm are equal to longer and longer forms of this expression:

(1 - x)(x² + 1)(x⁴ + 1)(x⁸ + 1). . .

Each evaluation of (2-q*qinv) is used compute the next factor to multiply qinv by to get a next value of qinv. These values can skip the lowest factors of the expression above when the initial qinv is greater than one; the factors would be different but the end result will have same functionality because the algorithm retains the values in the low bit positions of qinv that will result in 00..001 when q is multiplied by qinv.

2012-08-05, 20:03	#25
only_human "Gang aft agley" Sep 2002 2×1,877 Posts	Now the meat of the iterations. I'm going to try to show it in very basic notation with very few words starting from the qinv value of 1. x = 2z q = x+1 qinv =1 any iteration:{ t = qqinv; qinv = qinv (2-t) } a few steps through it: iteration 1: t = (x+1)1 = x + 1 2-t = -x + 1 qinv = qinv_prev(2-t) = -x + 1 Iteration 2: t = q * qinv = - x² + 1 2-t = x² + 1 qinv = qinv_prev(2-t) = - x³ + x² - x + 1 Iteration 3: 2-t = x⁴ + 1 qinv = qinv_prev (2-t) = - x⁷ + x⁶- x⁵ + x⁴ - x³ + x² - x + 1 What happens with t is all the inner terms vanish leaving only the first and last terms. In this iteration I show t in detail Iteration 4: t = q * qinv = (x + 1) * qinv = (x + 1) * (- x⁷ + x⁶- x⁵ + x⁴ - x³ + x² - x + 1) = - x⁸ + x⁷- x⁶ + x⁵ - x⁴ + x³ - x² + x +(- x⁷ + x⁶- x⁵ + x⁴ - x³ + x² - x + 1) = -x⁸ + 1 2-t = x⁸ + 1 qinv = (2-t) * qinv_prev = (x⁸ + 1)(- x⁷ + x⁶- x⁵ + x⁴ - x³ + x² - x + 1) = - x¹⁵ + x¹⁴. . . -x + 1 I've hidden a factor of two inside x for convenience. xⁿ is the same as 2ⁿzⁿ. The sign changing caused by 2-t could be simplified by using a precomputed -q instead of q when t is calculated and then just adding 2 but at best removes a single neg instruction. Sigma notation would be better but this will do for now. Looking at this offers hints to extending to multiword computations. Last fiddled with by only_human on 2012-08-05 at 20:26*

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Inverse of Smoothness Probability	paul0	Math	6	2017-07-25 16:41
mi64: inverse does not exist	wreck	NFS@Home	1	2016-05-08 15:44
Inverse of functions	Raman	Math	5	2011-04-13 23:29
Inverse Laplace Transform	flouran	Math	1	2010-01-18 23:48
Google.com's unhealthy obsession with famous mathematical constants	ewmayer	Lounge	3	2005-08-21 18:09

2012-08-10, 02:47	#27
only_human "Gang aft agley" Sep 2002 3754₁₀ Posts	x=2z q=x+1 if qinv is started with a value of 1, successive iterations of this mod inverse algorithm are equal to longer and longer forms of this expression: (1 - x)(x² + 1)(x⁴ + 1)(x⁸ + 1). . . Each evaluation of (2-q*qinv) is used compute the next factor to multiply qinv by to get a next value of qinv. These values can skip the lowest factors of the expression above when the initial qinv is greater than one; the factors would be different but the end result will have same functionality because the algorithm retains the values in the low bit positions of qinv that will result in 00..001 when q is multiplied by qinv.