156 lines · plain
1/* e(a, b, m) := a^b (mod m) */2define e(a, b, m) {3 auto s, sb;4 5 sb = obase; obase = 16;6 s = 1;7 while(b != 0) {8 if((b % 2) == 1) {9 s = (s * a) % m;10 }11 b /= 2;12 a = (a * a) % m;13 }14 obase = sb;15 return (s);16}17 18/* g(a, b) := (a, b) */19define g(a, b) {20 auto r;21 22 while(b != 0) {23 r = a % b;24 a = b;25 b = r;26 }27 if(a < 0) {28 return(-a);29 } else {30 return(a);31 }32}33 34define a(x) {35 if(x < 0) {36 return (-x);37 } else {38 return (x);39 }40}41 42xgu = 0; xgv = 0;43define x(a, b) {44 auto u, v, x, y, t, r;45 46 if(a(b) > a(a)) {47 t = b; b = a; a = t; r = 1;48 } else {49 r = 0;50 }51 52 u = 1; v = 0;53 x = 0; y = 1;54 55 while(b != 0) {56 t = a / b;57 58 a = a - (t * b);59 v = v - (t * y);60 u = u - (t * x);61 62 if(a(a) < a(b)) {63 t = a; a = b; b = t;64 t = v; v = y; y = t;65 t = u; u = x; x = t;66 }67 }68 69 if(r) {70 xgu = v; xgv = u;71 } else {72 xgu = u; xgv = v;73 }74 75 if(a < 0) {76 return (-a);77 } else {78 return (a);79 }80}81 82define i(a, m) {83 auto c;84 85 c = x(a, m);86 if(c != 1)87 return(0);88 89 return ((xgu + m) % m);90}91 92scale = 093rand_modulus = 286038514794rand_base = 12995rand_seed = 1034279996 97define srand(s) {98 rand_seed = s;99}100 101define rand(n) {102 auto r;103 104 r = (rand_seed * rand_base) % rand_modulus;105 rand_seed = r;106 return(r % n);107}108 109define rand_digits(k) {110 auto s;111 112 s = 0;113 while(k > 0) {114 s = (s * 10) + rand(10);115 k = k - 1;116 }117 118 return(s);119}120 121define rval(ndigits, probneg) {122 auto x;123 x = rand_digits(ndigits);124 if(probneg > 0 && rand(100) < probneg)125 x = x * -1;126 return(x);127}128 129for(i = 2; i < 100; i += 4) {130 value = rand_digits(i);131 obase = 256;132 print "readuns:", value;133 obase = 10;134 print ":", value, "\n" 135}136 137/*138for(i = 2; i < 100; i += 4) {139 for(j = 0; j < 2; ++j) {140 ndig = rand(7);141 base = rval(ndig, 20);142 expt = rand_digits(i);143 mod = rand_digits(i);144 145 result = e(base, expt, mod);146 if(result < 0) {147 result = result + mod;148 }149 print "emodbv:", base, ",", expt, ",", mod, ",0:", result, "\n";150 print "emodbv:", base, ",", expt, ",", mod, ",=2:", result, "\n";151 print "emodbv:", base, ",", expt, ",", mod, ",=3:", result, "\n";152 }153}154*/155halt156