| 1 |
/******************************************************************************* |
| 2 |
* * |
| 3 |
* Copyright (c) Martin Nicolay, 22. Nov. 1988 * |
| 4 |
* * |
| 5 |
* Wenn diese (oder sinngemaess uebersetzte) Copyright-Angabe enthalten * |
| 6 |
* bleibt, darf diese Source fuer jeden nichtkomerziellen Zweck weiter * |
| 7 |
* verwendet werden. * |
| 8 |
* * |
| 9 |
* martin@trillian.megalon.de * |
| 10 |
* * |
| 11 |
*******************************************************************************/ |
| 12 |
|
| 13 |
#include "arith.h" |
| 14 |
|
| 15 |
/* |
| 16 |
* !!!!!!!!!!!!!!!!!!!!!!!!!!!! ACHTUNG !!!!!!!!!!!!!!!!!!!!!!!!!!!! |
| 17 |
* Es findet keinerlei Ueberpruefung auf Bereichsueberschreitung |
| 18 |
* statt. Alle Werte muessen natuerliche Zahlen aus dem Bereich |
| 19 |
* 0 ... (MAXINT+1)^MAXLEN-1 sein. |
| 20 |
* |
| 21 |
* |
| 22 |
* Bei keiner Funktion oder Hilsfunktion werden Annahmen getroffen, |
| 23 |
* ueber die Verschiedenheit von Eingabe- & Ausgabe-Werten. |
| 24 |
* |
| 25 |
* |
| 26 |
* Funktionen: |
| 27 |
* |
| 28 |
* a_add( s1, s2, d ) |
| 29 |
* NUMBER *s1,*s2,*d; |
| 30 |
* *d = *s1 + *s2; |
| 31 |
* |
| 32 |
* a_assign( *d, *s ) |
| 33 |
* NUMBER *d,*s; |
| 34 |
* *d = *s; |
| 35 |
* |
| 36 |
* int a_cmp( c1, c2 ) |
| 37 |
* NUMBER *c1,*c2; |
| 38 |
* 1 : falls *c1 > *c2 |
| 39 |
* 0 : falls *c1 == *c2 |
| 40 |
* -1 : falls *c1 < *c2 |
| 41 |
* |
| 42 |
* a_div( d1, d2, q, r ) |
| 43 |
* NUMBER *d1,*d2,*q,*r; |
| 44 |
* *q = *d1 / *d2 Rest *r; |
| 45 |
* |
| 46 |
* a_div2( n ) |
| 47 |
* NUMBER *n; |
| 48 |
* *n /= 2; |
| 49 |
* |
| 50 |
* a_ggt( a, b, f ) |
| 51 |
* NUMBER *a,*b,*f; |
| 52 |
* *f = ( *a, *b ); |
| 53 |
* |
| 54 |
* a_imult( n, m, d ) |
| 55 |
* NUMBER *n; |
| 56 |
* INT m; |
| 57 |
* NUMBER *d; |
| 58 |
* *d = *n * m |
| 59 |
* |
| 60 |
* a_mult( m1, m2, d ) |
| 61 |
* NUMBER *m1,*m2,*d; |
| 62 |
* *d = *m1 * *m2; |
| 63 |
* |
| 64 |
* a_sub( s1, s2, d ) |
| 65 |
* NUMBER *s1,*s2,*d; |
| 66 |
* *d = *s1 - *s2; |
| 67 |
* |
| 68 |
* Modulare Funktionen |
| 69 |
* m_init( n, o ) |
| 70 |
* NUMBER *n,*o; |
| 71 |
* Initialsierung der Modularen Funktionen |
| 72 |
* o != 0 : *o = alter Wert |
| 73 |
* |
| 74 |
* m_add( s1, s2, d ) |
| 75 |
* NUMBER *s1, *s2, *d; |
| 76 |
* *d = *s1 + *s2; |
| 77 |
* |
| 78 |
* m_mult( m1, m2, d ) |
| 79 |
* NUMBER *m1,*m2,*d; |
| 80 |
* |
| 81 |
* m_exp( x, n, z ) |
| 82 |
* NUMBER *x,*n,*z; |
| 83 |
* *z = *x exp *n; |
| 84 |
* |
| 85 |
* |
| 86 |
* Hilfs-Funktionen: |
| 87 |
* |
| 88 |
* int n_bits( n, b ) |
| 89 |
* NUMBER *n; |
| 90 |
* int b; |
| 91 |
* return( unterste b Bits der Dualdarstellung von n) |
| 92 |
* |
| 93 |
* n_div( d1, z2, q, r ) |
| 94 |
* NUMBER *d1,z2[MAXBIT],*q,*r; |
| 95 |
* *q = *d1 / z2[0] Rest *r; |
| 96 |
* z2[i] = z2[0] * 2^i, i=0..MAXBIT-1 |
| 97 |
* |
| 98 |
* int n_cmp( i1, i2, l ) |
| 99 |
* INT i1[l], i2[l]; |
| 100 |
* 1 : falls i1 > i2 |
| 101 |
* 0 : falls i1 == i2 |
| 102 |
* -1 : falls i1 < i2 |
| 103 |
* |
| 104 |
* int n_mult( n, m, d, l) |
| 105 |
* INT n[l], m, d[]; |
| 106 |
* d = m * n; |
| 107 |
* return( sizeof(d) ); d.h. 'l' oder 'l+1' |
| 108 |
* |
| 109 |
* int n_sub( p1, p2, p3, l, lo ) |
| 110 |
* INT p1[l], p2[lo], p3[]; |
| 111 |
* p3 = p1 - p2; |
| 112 |
* return( sizeof(p3) ); d.h. '<= min(l,lo)' |
| 113 |
* |
| 114 |
* int n_bitlen( n ) |
| 115 |
* NUMBER *n; |
| 116 |
* return( sizeof(n) in bits ) |
| 117 |
* |
| 118 |
*/ |
| 119 |
|
| 120 |
|
| 121 |
/* |
| 122 |
* Konstante 1, 2 |
| 123 |
*/ |
| 124 |
NUMBER a_one = { |
| 125 |
1, |
| 126 |
{ (INT)1, }, |
| 127 |
}; |
| 128 |
|
| 129 |
NUMBER a_two = { |
| 130 |
#if MAXINT == 1 |
| 131 |
2, |
| 132 |
{ 0, (INT)1, }, |
| 133 |
#else |
| 134 |
1, |
| 135 |
{ (INT)2, }, |
| 136 |
#endif |
| 137 |
}; |
| 138 |
|
| 139 |
|
| 140 |
/* |
| 141 |
* Vergleiche zwei INT arrays der Laenge l |
| 142 |
*/ |
| 143 |
int n_cmp( i1, i2, l ) |
| 144 |
INT *i1,*i2; |
| 145 |
{ |
| 146 |
i1 += (l-1); /* Pointer ans Ende */ |
| 147 |
i2 += (l-1); |
| 148 |
|
| 149 |
for (;l--;) |
| 150 |
if ( *i1-- != *i2-- ) |
| 151 |
return( i1[1] > i2[1] ? 1 : -1 ); |
| 152 |
|
| 153 |
return(0); |
| 154 |
} |
| 155 |
|
| 156 |
/* |
| 157 |
* Vergleiche zwei NUMBER |
| 158 |
*/ |
| 159 |
int a_cmp( c1, c2 ) |
| 160 |
NUMBER *c1,*c2; |
| 161 |
{ |
| 162 |
int l; |
| 163 |
/* bei verschiedener Laenge klar*/ |
| 164 |
if ( (l=c1->n_len) != c2->n_len) |
| 165 |
return( l - c2->n_len); |
| 166 |
|
| 167 |
/* vergleiche als arrays */ |
| 168 |
return( n_cmp( c1->n_part, c2->n_part, l) ); |
| 169 |
} |
| 170 |
|
| 171 |
/* |
| 172 |
* Zuweisung einer NUMBER (d = s) |
| 173 |
*/ |
| 174 |
void a_assign( d, s ) |
| 175 |
NUMBER *d,*s; |
| 176 |
{ |
| 177 |
int l; |
| 178 |
|
| 179 |
if (s == d) /* nichts zu kopieren */ |
| 180 |
return; |
| 181 |
|
| 182 |
if ((l=s->n_len)) |
| 183 |
memcpy( d->n_part, s->n_part, sizeof(INT)*l); |
| 184 |
|
| 185 |
d->n_len = l; |
| 186 |
} |
| 187 |
|
| 188 |
/* |
| 189 |
* Addiere zwei NUMBER (d = s1 + s2) |
| 190 |
*/ |
| 191 |
void a_add( s1, s2, d ) |
| 192 |
NUMBER *s1,*s2,*d; |
| 193 |
{ |
| 194 |
int l,lo,ld,same; |
| 195 |
register LONG sum; |
| 196 |
register INT *p1,*p2,*p3; |
| 197 |
register INT b; |
| 198 |
|
| 199 |
/* setze s1 auch die groessere Zahl */ |
| 200 |
l = s1->n_len; |
| 201 |
if ( (l=s1->n_len) < s2->n_len ) { |
| 202 |
NUMBER *tmp = s1; |
| 203 |
|
| 204 |
s1 = s2; |
| 205 |
s2 = tmp; |
| 206 |
|
| 207 |
l = s1->n_len; |
| 208 |
} |
| 209 |
|
| 210 |
ld = l; |
| 211 |
lo = s2->n_len; |
| 212 |
p1 = s1->n_part; |
| 213 |
p2 = s2->n_part; |
| 214 |
p3 = d->n_part; |
| 215 |
same = (s1 == d); |
| 216 |
sum = 0; |
| 217 |
|
| 218 |
while (l --) { |
| 219 |
if (lo) { /* es ist noch was von s2 da */ |
| 220 |
lo--; |
| 221 |
b = *p2++; |
| 222 |
} |
| 223 |
else |
| 224 |
b = 0; /* ansonten 0 nehmen */ |
| 225 |
|
| 226 |
sum += (LONG)*p1++ + (LONG)b; |
| 227 |
*p3++ = TOINT(sum); |
| 228 |
|
| 229 |
if (sum > (LONG)MAXINT) { /* carry merken */ |
| 230 |
sum = 1; |
| 231 |
} |
| 232 |
else |
| 233 |
sum = 0; |
| 234 |
|
| 235 |
if (!lo && same && !sum) /* nichts mehr zu tuen */ |
| 236 |
break; |
| 237 |
} |
| 238 |
|
| 239 |
if (sum) { /* letztes carry beruecksichtigen */ |
| 240 |
ld++; |
| 241 |
*p3 = sum; |
| 242 |
} |
| 243 |
|
| 244 |
d->n_len = ld; /* Laenge setzen */ |
| 245 |
} |
| 246 |
|
| 247 |
/* |
| 248 |
* Subtrahiere zwei INT arrays. return( Laenge Ergebniss ) |
| 249 |
* l == Laenge p1 |
| 250 |
* lo== Laenge p3 |
| 251 |
*/ |
| 252 |
int n_sub( p1, p2, p3, l, lo ) |
| 253 |
INT *p1,*p2,*p3; |
| 254 |
int l,lo; |
| 255 |
{ |
| 256 |
int ld,lc,same; |
| 257 |
int over = 0; |
| 258 |
register LONG dif; |
| 259 |
LONG a,b; |
| 260 |
|
| 261 |
same = (p1 == p3); /* frueher Abbruch moeglich */ |
| 262 |
|
| 263 |
for (lc=1, ld=0; l--; lc++) { |
| 264 |
a = (LONG)*p1++; |
| 265 |
if (lo) { /* ist noch was von p2 da ? */ |
| 266 |
lo--; |
| 267 |
b = (LONG)*p2++; |
| 268 |
} |
| 269 |
else |
| 270 |
b=0; /* ansonten 0 nehmen */ |
| 271 |
|
| 272 |
if (over) /* frueherer Overflow */ |
| 273 |
b++; |
| 274 |
if ( b > a ) { /* jetzt Overflow ? */ |
| 275 |
over = 1; |
| 276 |
dif = (MAXINT +1) + a; |
| 277 |
} |
| 278 |
else { |
| 279 |
over = 0; |
| 280 |
dif = a; |
| 281 |
} |
| 282 |
dif -= b; |
| 283 |
*p3++ = (INT)dif; |
| 284 |
|
| 285 |
if (dif) /* Teil != 0 : Laenge neu */ |
| 286 |
ld = lc; |
| 287 |
if (!lo && same && !over) { /* nichts mehr zu tuen */ |
| 288 |
if (l > 0) /* Laenge korrigieren */ |
| 289 |
ld = lc + l; |
| 290 |
break; |
| 291 |
} |
| 292 |
} |
| 293 |
|
| 294 |
return( ld ); |
| 295 |
} |
| 296 |
|
| 297 |
/* |
| 298 |
* Subtrahiere zwei NUMBER (d= s1 - s2) |
| 299 |
*/ |
| 300 |
void a_sub( s1, s2, d ) |
| 301 |
NUMBER *s1,*s2,*d; |
| 302 |
{ |
| 303 |
d->n_len = n_sub( s1->n_part, s2->n_part, d->n_part |
| 304 |
,s1->n_len, s2->n_len ); |
| 305 |
} |
| 306 |
|
| 307 |
/* |
| 308 |
* Mulitipliziere INT array der Laenge l mit einer INT (d = n * m) |
| 309 |
* return neue Laenge |
| 310 |
*/ |
| 311 |
int n_mult( n, m, d, l) |
| 312 |
register INT *n; |
| 313 |
register INT m; |
| 314 |
INT *d; |
| 315 |
{ |
| 316 |
int i; |
| 317 |
register LONG mul; |
| 318 |
|
| 319 |
for (i=l,mul=0; i; i--) { |
| 320 |
mul += (LONG)m * (LONG)*n++; |
| 321 |
*d++ = TOINT(mul); |
| 322 |
mul = DIVMAX1( mul ); |
| 323 |
} |
| 324 |
|
| 325 |
if (mul) { /* carry ? */ |
| 326 |
l++; |
| 327 |
*d = mul; |
| 328 |
} |
| 329 |
|
| 330 |
return( l ); |
| 331 |
} |
| 332 |
|
| 333 |
/* |
| 334 |
* Mulitipliziere eine NUMBER mit einer INT (d = n * m) |
| 335 |
*/ |
| 336 |
void a_imult( n, m, d ) |
| 337 |
NUMBER *n; |
| 338 |
INT m; |
| 339 |
NUMBER *d; |
| 340 |
{ |
| 341 |
if (m == 0) |
| 342 |
d->n_len=0; |
| 343 |
else if (m == 1) |
| 344 |
a_assign( d, n ); |
| 345 |
else |
| 346 |
d->n_len = n_mult( n->n_part, m, d->n_part, n->n_len ); |
| 347 |
} |
| 348 |
|
| 349 |
/* |
| 350 |
* Multipliziere zwei NUMBER (d = m1 * m2) |
| 351 |
*/ |
| 352 |
void a_mult( m1, m2, d ) |
| 353 |
NUMBER *m1,*m2,*d; |
| 354 |
{ |
| 355 |
static INT id[ MAXLEN ]; /* Zwischenspeicher */ |
| 356 |
register INT *vp; /* Pointer darin */ |
| 357 |
register LONG sum; /* Summe fuer jede Stelle */ |
| 358 |
register LONG tp1; /* Zwischenspeicher fuer m1 */ |
| 359 |
register INT *p2; |
| 360 |
INT *p1; |
| 361 |
int l1,l2,ld,lc,l,i,j; |
| 362 |
|
| 363 |
l1 = m1->n_len; |
| 364 |
l2 = m2->n_len; |
| 365 |
l = l1 + l2; |
| 366 |
if (l >= MAXLEN) |
| 367 |
abort(); |
| 368 |
|
| 369 |
for (i=l, vp=id; i--;) |
| 370 |
*vp++ = 0; |
| 371 |
|
| 372 |
/* ohne Uebertrag in Zwischenspeicher multiplizieren */ |
| 373 |
for ( p1 = m1->n_part, i=0; i < l1 ; i++, p1++ ) { |
| 374 |
|
| 375 |
tp1 = (LONG)*p1; |
| 376 |
vp = &id[i]; |
| 377 |
sum = 0; |
| 378 |
for ( p2 = m2->n_part, j = l2; j--;) { |
| 379 |
sum += (LONG)*vp + (tp1 * (LONG)*p2++); |
| 380 |
*vp++ = TOINT( sum ); |
| 381 |
sum = DIVMAX1(sum); |
| 382 |
} |
| 383 |
*vp++ += (INT)sum; |
| 384 |
} |
| 385 |
|
| 386 |
/* jetzt alle Uebertraege beruecksichtigen */ |
| 387 |
ld = 0; |
| 388 |
for (lc=0, vp=id, p1=d->n_part; lc++ < l;) { |
| 389 |
if (( *p1++ = *vp++ )) |
| 390 |
ld = lc; |
| 391 |
} |
| 392 |
|
| 393 |
d->n_len = ld; |
| 394 |
} |
| 395 |
|
| 396 |
|
| 397 |
/* |
| 398 |
* Dividiere Zwei NUMBER mit Rest (q= d1 / z2[0] Rest r) |
| 399 |
* z2[i] = z2[0] * 2^i, i=0..MAXBIT-1 |
| 400 |
* r = 0 : kein Rest |
| 401 |
* q = 0 : kein Quotient |
| 402 |
*/ |
| 403 |
void n_div( d1, z2, q, r ) |
| 404 |
NUMBER *d1,*z2,*q,*r; |
| 405 |
{ |
| 406 |
static NUMBER dummy_rest; /* Dummy Variable, falls r = 0 */ |
| 407 |
static NUMBER dummy_quot; /* Dummy Variable, falla q = 0 */ |
| 408 |
INT *i1,*i1e,*i3; |
| 409 |
int l2,ld,l,lq; |
| 410 |
#if MAXINT != 1 |
| 411 |
INT z; |
| 412 |
int pw,l2t; |
| 413 |
#endif |
| 414 |
|
| 415 |
if (!z2->n_len) |
| 416 |
abort(); |
| 417 |
|
| 418 |
if (!r) |
| 419 |
r = &dummy_rest; |
| 420 |
if (!q) |
| 421 |
q = &dummy_quot; |
| 422 |
|
| 423 |
a_assign( r, d1 ); /* Kopie von d1 in den Rest */ |
| 424 |
|
| 425 |
l2= z2->n_len; /* Laenge von z2[0] */ |
| 426 |
l = r->n_len - l2; /* Laenge des noch ''rechts'' liegenden |
| 427 |
Stuecks von d1 */ |
| 428 |
lq= l +1; /* Laenge des Quotienten */ |
| 429 |
i3= q->n_part + l; |
| 430 |
i1= r->n_part + l; |
| 431 |
ld = l2; /* aktuelle Laenge des ''Vergleichsstuecks'' |
| 432 |
von d1 */ |
| 433 |
i1e= i1 + (ld-1); |
| 434 |
|
| 435 |
for (; l >= 0; ld++, i1--, i1e--, l--, i3--) { |
| 436 |
*i3 = 0; |
| 437 |
|
| 438 |
if (ld == l2 && ! *i1e) { |
| 439 |
ld--; |
| 440 |
continue; |
| 441 |
} |
| 442 |
|
| 443 |
if ( ld > l2 || (ld == l2 && n_cmp( i1, z2->n_part, l2) >= 0 ) ) { |
| 444 |
#if MAXINT != 1 |
| 445 |
/* nach 2er-Potenzen zerlegen */ |
| 446 |
for (pw=MAXBIT-1, z=(INT)HIGHBIT; pw >= 0; pw--, z /= 2) { |
| 447 |
if ( ld > (l2t= z2[pw].n_len) |
| 448 |
|| (ld == l2t |
| 449 |
&& n_cmp( i1, z2[pw].n_part, ld) >= 0) ) { |
| 450 |
ld = n_sub( i1, z2[pw].n_part, i1, ld, l2t ); |
| 451 |
(*i3) += z; |
| 452 |
} |
| 453 |
} |
| 454 |
#else |
| 455 |
/* bei MAXINT == 1 alles viel einfacher */ |
| 456 |
ld = n_sub( i1, z2->n_part, i1, ld, l2 ); |
| 457 |
(*i3) ++; |
| 458 |
#endif |
| 459 |
} |
| 460 |
} |
| 461 |
|
| 462 |
/* Korrektur, falls l von Anfang an Negativ war */ |
| 463 |
l ++; |
| 464 |
lq -= l; |
| 465 |
ld += l; |
| 466 |
|
| 467 |
if (lq>0 && !q->n_part[lq -1]) /* evtl. Laenge korrigieren */ |
| 468 |
lq--; |
| 469 |
|
| 470 |
q->n_len = lq; |
| 471 |
r->n_len = ld -1; |
| 472 |
} |
| 473 |
|
| 474 |
/* |
| 475 |
* Dividiere Zwei NUMBER mit Rest (q= d1 / z2[0] Rest r) |
| 476 |
* z2[i] = z2[0] * 2^i, i=0..MAXBIT-1 |
| 477 |
* r = 0 : kein Rest |
| 478 |
* q = 0 : kein Quotient |
| 479 |
*/ |
| 480 |
void a_div( d1, d2, q, r ) |
| 481 |
NUMBER *d1,*d2,*q,*r; |
| 482 |
{ |
| 483 |
#if MAXINT != 1 |
| 484 |
NUMBER z2[MAXBIT]; |
| 485 |
INT z; |
| 486 |
int i; |
| 487 |
|
| 488 |
a_assign( &z2[0], d2 ); |
| 489 |
for (i=1,z=2; i < MAXBIT; i++, z *= 2) |
| 490 |
a_imult( d2, z, &z2[i] ); |
| 491 |
|
| 492 |
d2 = z2; |
| 493 |
#endif |
| 494 |
|
| 495 |
n_div( d1, d2, q, r ); |
| 496 |
} |
| 497 |
|
| 498 |
/* |
| 499 |
* Dividiere eine NUMBER durch 2 |
| 500 |
*/ |
| 501 |
void a_div2( n ) |
| 502 |
NUMBER *n; |
| 503 |
{ |
| 504 |
#if MAXBIT == LOWBITS |
| 505 |
register INT *p; |
| 506 |
int i; |
| 507 |
|
| 508 |
#if MAXINT != 1 |
| 509 |
register INT h; |
| 510 |
register int c; |
| 511 |
|
| 512 |
c=0; |
| 513 |
i= n->n_len; |
| 514 |
p= &n->n_part[i-1]; |
| 515 |
|
| 516 |
for (; i--;) { |
| 517 |
if (c) { |
| 518 |
c = (h= *p) & 1; |
| 519 |
h /= 2; |
| 520 |
h |= HIGHBIT; |
| 521 |
} |
| 522 |
else { |
| 523 |
c = (h= *p) & 1; |
| 524 |
h /= 2; |
| 525 |
} |
| 526 |
|
| 527 |
*p-- = h; |
| 528 |
} |
| 529 |
|
| 530 |
if ( (i= n->n_len) && n->n_part[i-1] == 0 ) |
| 531 |
n->n_len = i-1; |
| 532 |
|
| 533 |
#else /* MAXBIT != 1 */ |
| 534 |
p = n->n_part; |
| 535 |
i = n->n_len; |
| 536 |
|
| 537 |
if (i) { |
| 538 |
n->n_len = i-1; |
| 539 |
for (; --i ; p++) |
| 540 |
p[0] = p[1]; |
| 541 |
} |
| 542 |
#endif /* MAXBIT != 1 */ |
| 543 |
#else /* MAXBIT == LOWBITS */ |
| 544 |
a_div( n, &a_two, n, NUM0P ); |
| 545 |
#endif /* MAXBIT == LOWBITS */ |
| 546 |
} |
| 547 |
|
| 548 |
|
| 549 |
/* |
| 550 |
* MODULO-FUNKTIONEN |
| 551 |
*/ |
| 552 |
|
| 553 |
static NUMBER mod_z2[ MAXBIT ]; |
| 554 |
|
| 555 |
/* |
| 556 |
* Init |
| 557 |
*/ |
| 558 |
void m_init( n, o ) |
| 559 |
NUMBER *n,*o; |
| 560 |
{ |
| 561 |
INT z; |
| 562 |
int i; |
| 563 |
|
| 564 |
if (o) |
| 565 |
a_assign( o, &mod_z2[0] ); |
| 566 |
|
| 567 |
if (! a_cmp( n, &mod_z2[0] ) ) |
| 568 |
return; |
| 569 |
|
| 570 |
for (i=0,z=1; i < MAXBIT; i++, z *= 2) |
| 571 |
a_imult( n, z, &mod_z2[i] ); |
| 572 |
} |
| 573 |
|
| 574 |
void m_add( s1, s2, d ) |
| 575 |
NUMBER *s1, *s2, *d; |
| 576 |
{ |
| 577 |
a_add( s1, s2, d ); |
| 578 |
if (a_cmp( d, mod_z2 ) >= 0) |
| 579 |
a_sub( d, mod_z2, d ); |
| 580 |
} |
| 581 |
|
| 582 |
void m_mult( m1, m2, d ) |
| 583 |
NUMBER *m1,*m2,*d; |
| 584 |
{ |
| 585 |
a_mult( m1, m2, d ); |
| 586 |
n_div( d, mod_z2, NUM0P, d ); |
| 587 |
} |
| 588 |
|
| 589 |
/* |
| 590 |
* Restklassen Exponent |
| 591 |
*/ |
| 592 |
void m_exp( x, n, z ) |
| 593 |
NUMBER *x,*n,*z; |
| 594 |
{ |
| 595 |
NUMBER xt,nt; |
| 596 |
|
| 597 |
a_assign( &nt, n ); |
| 598 |
a_assign( &xt, x ); |
| 599 |
a_assign( z, &a_one ); |
| 600 |
|
| 601 |
while (nt.n_len) { |
| 602 |
while ( ! (nt.n_part[0] & 1) ) { |
| 603 |
m_mult( &xt, &xt, &xt ); |
| 604 |
a_div2( &nt ); |
| 605 |
} |
| 606 |
m_mult( &xt, z, z ); |
| 607 |
a_sub( &nt, &a_one, &nt ); |
| 608 |
} |
| 609 |
} |
| 610 |
|
| 611 |
/* |
| 612 |
* GGT |
| 613 |
*/ |
| 614 |
void a_ggt( a, b, f ) |
| 615 |
NUMBER *a,*b,*f; |
| 616 |
{ |
| 617 |
NUMBER t[2]; |
| 618 |
int at,bt, tmp; |
| 619 |
|
| 620 |
a_assign( &t[0], a ); at= 0; |
| 621 |
a_assign( &t[1], b ); bt= 1; |
| 622 |
|
| 623 |
if ( a_cmp( &t[at], &t[bt] ) < 0 ) { |
| 624 |
tmp= at; at= bt; bt= tmp; |
| 625 |
} |
| 626 |
/* euklidischer Algorithmus */ |
| 627 |
while ( t[bt].n_len ) { |
| 628 |
a_div( &t[at], &t[bt], NUM0P, &t[at] ); |
| 629 |
tmp= at; at= bt; bt= tmp; |
| 630 |
} |
| 631 |
|
| 632 |
a_assign( f, &t[at] ); |
| 633 |
} |
| 634 |
|
| 635 |
/* |
| 636 |
* die untersten b bits der Dualdarstellung von n |
| 637 |
* die bits muessen in ein int passen |
| 638 |
*/ |
| 639 |
int n_bits(n,b) |
| 640 |
NUMBER *n; |
| 641 |
{ |
| 642 |
INT *p; |
| 643 |
int l; |
| 644 |
unsigned r; |
| 645 |
int m = (1<<b) -1; |
| 646 |
|
| 647 |
if ( n->n_len == 0) |
| 648 |
return(0); |
| 649 |
|
| 650 |
if (LOWBITS >= b) |
| 651 |
return( n->n_part[0] & m ); |
| 652 |
|
| 653 |
#if LOWBITS != 0 |
| 654 |
l = (b-1) / LOWBITS; |
| 655 |
#else |
| 656 |
l = n->n_len -1; |
| 657 |
#endif |
| 658 |
for (p= &n->n_part[l],r=0; l-- >= 0 && b > 0; b-= LOWBITS, p--) { |
| 659 |
r = MULMAX1( r ); |
| 660 |
r += (unsigned)*p; |
| 661 |
} |
| 662 |
|
| 663 |
return( r & m ); |
| 664 |
} |
| 665 |
|
| 666 |
/* |
| 667 |
* Anzahl der bits von n bei Dualdarstellung |
| 668 |
*/ |
| 669 |
int n_bitlen( n ) |
| 670 |
NUMBER *n; |
| 671 |
{ |
| 672 |
NUMBER b; |
| 673 |
int i; |
| 674 |
|
| 675 |
a_assign( &b, &a_one ); |
| 676 |
|
| 677 |
for (i=0; a_cmp( &b, n ) <= 0; a_mult( &b, &a_two, &b ), i++) |
| 678 |
; |
| 679 |
|
| 680 |
return(i); |
| 681 |
} |
Parent Directory
| 
Revision Log