# 基本代数

## 加法

任意3个个位数相加的和最多是两位数


$$k = log_b(N + 1)$$

## 乘法和除法

Decimal:     Binary:
11   3       1011  11
5    6       101  110
2   12       10  1100   #will delete
1   24       1  11000
---          -----
33         100001


1. 11除以2,取整为5;3乘以2为6
2. 5除以2,取整为2;6乘以2为12
3. 2除了2,为1;12乘以2为24
4. 去掉2那一行，因为2是偶数。
5. 最后相加：3 + 6 + 24 = 33

3 11
1 22
--
33


#include <stdio.h>
#include <stdlib.h>

/* multiple two integer A and B */
int multiple(int a, int b);

int main(int argc, char *argv[])
{
int i, j;

for (i = -1000; i < 1000; i++) {
for (j = -1000; j < 1000; j++) {
if (multiple(i, j) == i * j) {
printf("match!!\n");
} else {
printf("error!!\n");
exit(1);
}
}
}
printf("oh!successfully!!!\n");

return 0;
}

int multiple(int a, int b)
{
int sign, temp, sum;

if (a < 0) {
sign = -1;
a = -a;
} else {
sign = 1;
}
if (b < 0) {
sign = -sign;
b = -b;
}
if (a > b) {
temp = a;
a = b;
b = temp;
}
if (a == 0 || b == 0) {
return 0;
}

sum = 0;
while (a >= 1) {
if (a & 1) {
sum += b;
}
a >>= 1;
b <<= 1;
}
if (sign == -1) {
return -sum;
} else {
return sum;
}
}


#include <stdio.h>
#include <stdlib.h>

struct Div {
int quot;
int rem;
};

/* calculate DIVIDER / DIVISOR, return the quotient and remainder
* in struct Div. */
struct Div divide(int divider, int divisor);

int main(int argc, char *argv[])
{
int i, j;
struct Div d;

for (i = -10; i < 10; i++) {
for (j = 1; j < 100; j++) {
d = divide(i, j);
if (d.quot == i / j && d.rem == i % j) {
printf("match!!\n");
} else {
printf("%d / %d :error!\n", i, j);
exit(1);
}
}
}

return 0;
}

struct Div divide(int divider, int divisor)
{
struct Div div;
int sign, rem_sign;

if (divisor == 0) {
fprintf(stderr, "divisor can't be zero!");
exit(1);
}
if (divider == 0) {
div.quot = 0;
div.rem = 0;
return div;
}
if (divider < 0) {
sign = -1;
divider = -divider;
rem_sign = -1;
} else {
sign = 1;
rem_sign = 1;
}
if (divisor < 0) {
sign = -sign;
divisor = -divisor;
}
div.quot = div.rem = 0;
while (divider > 0) {
if (divider & 1) {
div.rem++;
}
divider >>= 1;
div.rem += divider;
while (div.rem >= divisor) {
div.quot++;
div.rem -= divisor;
}
}
if (sign == -1) {
div.quot = -div.quot;
}
if (rem_sign < 0) {
div.rem = -div.rem;
}

return div;
}


# 模代数

## 求模运算

$$x ≡ y (mod N) ↔ N divides (x - y)$$

x和y除了N有相同的余数当且仅当N整除(x - y)


... -6 -3 0 3 6 ...        //余数为0
... -5 -2 1 4 7 ...        //余数为1
... -4 -1 2 5 8 ...        //余数为2


2^345^ ≡ (2^5^)^69^ ≡ (32)^69^ ≡ (mod 31) 因为32 ≡ 1 (mod 31), 32 ≡ 1 (mod 31)，所以 32^2^ ≡ 1^2^ (mod 31), … 32^69^ ≡ 1^69^ ≡ 1 (mod 31) = 1

c ≡ (a * b) (mod N) c ≡ (a * (b (mod N))) (mod N)

a^2^ (mod N) ≡ (a * (a (mod N))) (mod N) a^3^ (mod N) ≡ (a * ((a * (a (mod N))) (mod N))) (mod N) …

#include <stdio.h>

/* calculate BASE^EXP % MOD, return the result */
int mod_pow(int base, int exp, int mod);

int main(int argc, char *argv[])
{
printf("%d\n", mod_pow(4, 13, 497));

return 0;
}

int mod_pow(int base, int exp, int mod)
{
int i, inter_base, result;

result = 1;
for (i = 0; i < exp; i++) {
inter_base = base * result;
result = inter_base % mod;
}
return result;
}


#include <stdio.h>

/* calculate BASE^EXP % MOD, EXP >= 0, return the result */
int mod_pow(int base, int exp, int mod);

int main(int argc, char *argv[])
{
printf("%d\n", mod_pow(4, 13, 497));

return 0;
}

int mod_pow(int base, int exp, int mod)
{
int result;

result = 1;
while (exp > 0) {
if (exp & 1) {
result = (result * base) % mod;
}
exp >>= 1;
base = (base * base) % mod;
}

return result;
}


(a * b) % m = ((a % m) * (b % m)) % m


## 欧几里得最大公约数算法

对于两个正整数x和y，有x >= y，则gcd(x, y) = gcd(x mod y, y).


有2个正整数x, y, x >= y, 它们的最大公约数是gcd。



#include <stdio.h>

/* return the greatest common divisor with x, y >= 0,
* implement using recursive method. */
int gcd_r(int x, int y);

/* return the greatest common divisor with x, y >= 0,
* implement using non-recursive method. */
int gcd(int x, int y);

int main(int argc, char *argv[])
{
printf("%d\n", gcd_r(1035, 759));
printf("%d\n", gcd(1035, 759));

return 0;
}

int gcd_r(int x, int y)
{
int temp;

if (x < y) {
temp = x;
x = y;
y = temp;
}
if (y == 0) {
return x;
} else {
return gcd_r(y, x % y);
}
}

int gcd(int x, int y)
{
int temp;

if (x < y) {
temp = x;
x = y;
y = temp;
}
while (y > 0) {
temp = y;
y = x % y;
x = temp;
}
return x;
}


## 扩展欧几里得算法

对于不全为0的正整数a和b，gcd(a, b)表示a和b的最大公约数，则必然存在整数对
x和y，使得gcd(a, b) = ax + by


对于不定方程ax + by = c，已经a, b, c的值，求解满足方程的一组x, y。



ax~1~ / gcd(a, b) + by~1~ / gcd(a, b) = 1，两边再同时乘以c，得到：

ax~1~ * (c / gcd(a, b)) + by~1~ * (c / gcd(a, b)) = c = ax + by,

x = x1 * (c / gcd(a, b))

y = y1 * (c / gcd(a, b))

x1 = 1, y1为任意整数，比如y1 = 0。

ax1 + by1 = gcd(a, b) = gcd(b, a % b) = bx2 + (a % b)y2

= bx2 + (a - (a / b) * b)y2 = bx2 + ay2 - (a / b) * b * y2

x1 = y2, y1 = x2 - (a / b)y2

#include <stdio.h>

/* extended euclidean algorithm:gcd(a, b) = ax + by
* return gcd(a, b) */
int extended_euclid(int a, int b, int *x, int *y);

/* solve the indefinite equation: ax + by = c,
* if no solution, return 0, otherwise return 1
* and set one solution in x and y. */
int indefinite_equation(int a, int b, int c, int *x, int *y);

int main(int argc, char *argv[])
{
int x, y;

if (indefinite_equation(2, 3, 8, &x, &y)) {
printf("x=%d, y=%d\n", x, y);
}

return 0;
}

int indefinite_equation(int a, int b, int c, int *x, int *y)
{
int gcd;

gcd = extended_euclid(a, b, x, y);
if (c % gcd != 0) {
return 0;
}
*x = *x * (c / gcd);
*y = *y * (c / gcd);
return 1;
}

int extended_euclid(int a, int b, int *x, int *y)
{
int x1, y1, gcd;

if ( b == 0) {
*x = 1;
*y = 0;
return a;
}
gcd = extended_euclid(b, a % b, &x1, &y1);
*x = y1;
*y = x1 - (a / b) * y1;

return gcd;
}


a^-1^ ≡ x (mod m)

ax ≡ aa^-1^ ≡ 1 (mod m)

a的乘法逆元存在当且仅当a与m互质。

ax ≡ 1 (mod m)

ax = qm + 1

ax - mq = 1

ax + by = gcd(a, b)

/* calculate the multiplicative inverse of (a mod m), return
* the inverse */
int mul_inverse(int a, int m);

int mul_inverse(int a, int m)
{
int inverse, y;

extended_euclid(a, m, &inverse, &y);

return inverse;
}


# 素性测试

primality testing. 合数的英文是composite.

# 费马小定理

fermat’s little theorem：

a^p-1^ ≡ 1 (mod p)

a^p^ ≡ a (mod p), 也可以写成：

a^p^ - a ≡ 0 (mod p)

typedef unsigned int uint;

/* judge whether an integer N is prime
* in terms of the definition. */
int is_prime_direct(uint n);

int is_prime_direct(uint n)
{
int i;

if (n < 2) {
return 0;
}
for (i = 2; i < n; i++) {
if (n % i == 0) {
return 0;
}
}
return 1;
}


typedef unsigned int uint;

/* judge whether an integer N is prime
* in terms of the definition and stop
* at n / 2. */
int is_prime_half(uint n);

int is_prime_half(uint n)
{
int i;

if (n < 2) {
return 0;
}
for (i = 2; i <= n / 2; i++) {
if (n % i == 0) {
return 0;
}
}
return 1;
}


51不能被2整除，53 / 2 = 26，余数为1

53不能被3整除，53 / 3 = 17，余数为2

53 不能被17整除, 53 / 17 = 3，余数为2

53不能被26整除，53 / 26 = 2，余数为1

#include <math.h>

typedef unsigned int uint;

/* judge whether an integer N is prime
* in terms of the definition and stop
* at sqrt(n). */
int is_prime_sqrt(uint n);

int is_prime_sqrt(uint n)
{
int i;

if (n < 2) {
return 0;
}
for (i = 2; i <= sqrt(n); i++) {
if (n % i == 0) {
return 0;
}
}
return 1;
}


a^n-1^ ≡ 1 (mod n)

/* judge whether an integer N is prime
* in terms of fermat's little theorem */
int is_prime_fermat(uint n);

/* calculate BASE^EXP % MOD, return the result */
int pow_mod(int base, int exp, int mod);

int is_prime_sqrt(uint n)
{
int i;

if (n < 2) {
return 0;
}
for (i = 2; i <= sqrt(n); i++) {
if (n % i == 0) {
return 0;
}
}
return 1;
}

int is_prime_fermat(uint n)
{
int base;

if (n < 2) {
return 0;
}
base = rand() % (n - 1) + 1;
if (pow_mod(base, n - 1, n) == 1) {
return 1;
} else {
return 0;
}
}

int pow_mod(int base, int exp, int mod)
{
int result;

result = 1;
while (exp > 0) {
if (exp & 1) {
result = (result * base) % mod;
}
base = (base * base) % mod;
exp >>= 1;
}
return result;
}


int is_prime_fermat(uint n)
{
int base, i;

if (n < 2) {
return 0;
}
for (i = 0; i < n / 2; i++) {
base = rand() % (n - 1) + 1;
if (pow_mod(base, n - 1, n) != 1) {
return 0;
}
}
return 1;
}