Here’s fnPad code to calculate the modular inverse.
// calculate the modular inverse
a = 5; b = 93
i = modi(a,b); i ≈ 56
i*a%b == 1 ≈ true // show that i is the modular inverse
// modular inverse of a mod b
modi(a,b) = mode(egcd(a,b),b)
// modular inverse given extended GCD (GCD must be 1)
mode(e,b) = ( e[1] == 1 ) ? e[2]%b + ( ( e[2] < 0 ) ? b : 0 ) : NaN
// extended greatest common divisor
egcd(a,b) = ( b == 0 ) ? { a, 1, 1 } : dcge(egcd(b,a%b),a/b)
// unwind from GCD; recurrence relation makes e[1] = e[2]*a + e[3]*b
dcge(e,q) = { e[1], e[3], e[2]-e[3]*q }
posted @ 07:39 AM EST
Here’s a reference for the algorithm used in the previously posted fnPad code that calculates the modular inverse. It looks to me as though there’s a bug in the pseudocode wherein the first returned vector should be { 1, 1 }.
posted @ 07:53 PM EST
The table of data below, released by the Pan-Mass Challenge, shows how unusual that event is in contributing 99% of funds raised to the charity it benefits.
Event | Raised | Participants | Contributed |
Pan-Mass Challenge | $26,000,000 | 4,271 | 99% |
Nike Women’s Marathon | $12,000,000 | 15,000 | 70% |
MS 150, Texas | $8,360,000 | 13,000 | 76% |
5 Livestrong Rides in US | $7,500,000 | 10,000 | 75% |
posted @ 08:16 PM EST