TAOCP 3.2.1.3: Potency

Section 3.2.1.3 exercises: 8/8 solved.

8 items

Section 3.2.1.3. Potency

Exercises from TAOCP Volume 2 Section 3.2.1.3: 8/8 solved.

#	Rating	Category	Status	Time
1	[M10]	math-simple	verified	1m19s
2	[10]	simple	verified	1m08s
3	[11]	simple	verified	1m28s
4	[15]	simple	verified	4m13s
5	[M20]	math-medium	verified	1m23s
6	▶ [20]	medium	verified	3m55s
7	[**]		verified	1m07s
8	▶ [**]		solved	5m08s

Practice › Mathematics › TAOCP › TAOCP Vol 2: Seminumerical Algorithms › TAOCP 3.2.1.3: Potency ›

TAOCP 3.2.1.3 Exercise 1

Let $a=B^2+1$, so that $b=a-1=B^2$.

Practice › Mathematics › TAOCP › TAOCP Vol 2: Seminumerical Algorithms › TAOCP 3.2.1.3: Potency ›

TAOCP 3.2.1.3 Exercise 2

In the MIX code (3) we have $a = B^2 + 1$, so $b = a - 1 = B^2$.

Practice › Mathematics › TAOCP › TAOCP Vol 2: Seminumerical Algorithms › TAOCP 3.2.1.3: Potency ›

TAOCP 3.2.1.3 Exercise 3

The potency is the least integer $s$ such that b^s \equiv 0 \pmod{m}, where $b=a-1$; equivalently, $m\mid b^s$.

Practice › Mathematics › TAOCP › TAOCP Vol 2: Seminumerical Algorithms › TAOCP 3.2.1.3: Potency ›

TAOCP 3.2.1.3 Exercise 4

Let $m = 2^e \ge 8$, and consider a linear congruential generator of the form X_{n+1} \equiv a X_n + c \pmod{m}.

Practice › Mathematics › TAOCP › TAOCP Vol 2: Seminumerical Algorithms › TAOCP 3.2.1.3: Potency ›

TAOCP 3.2.1.3 Exercise 5

Let $m = p_1^{e_1} \cdots p_r^{e_r}$ and $a = 1 + k p_1^{f_1} \cdots p_r^{f_r}$, where $k$ is relatively prime to $m$, and $a$ satisfies the conditions of Theorem 3.

Practice › Mathematics › TAOCP › TAOCP Vol 2: Seminumerical Algorithms › TAOCP 3.2.1.3: Potency ›

TAOCP 3.2.1.3 Exercise 6

We are asked to determine which values of $m = w \pm 1$ in Table 3.

Practice › Mathematics › TAOCP › TAOCP Vol 2: Seminumerical Algorithms › TAOCP 3.2.1.3: Potency ›

Since $a \equiv 1 + b \pmod{m}$, we have $aa' \equiv (1 + b)a' \equiv 1 \pmod{m}.$ Solving for $a'$, we obtain $(1 + b)a' \equiv 1 \pmod{m} \implies a' \equiv \frac{1}{1 + b} \pmod{m}.$ We can expand...

Practice › Mathematics › TAOCP › TAOCP Vol 2: Seminumerical Algorithms › TAOCP 3.2.1.3: Potency ›

TAOCP 3.2.1.3 Exercise 8

**Corrected Solution to Exercise 3.

TAOCP 3.2.1.3: Potency

Section 3.2.1.3. Potency

TAOCP 3.2.1.3 Exercise 1

TAOCP 3.2.1.3 Exercise 2

TAOCP 3.2.1.3 Exercise 3

TAOCP 3.2.1.3 Exercise 4

TAOCP 3.2.1.3 Exercise 5

TAOCP 3.2.1.3 Exercise 6

TAOCP 3.2.1.3 Exercise 7

TAOCP 3.2.1.3 Exercise 8