TAOCP 4.5.4: Factoring into Primes
Section 4.5.4 exercises: 46/46 solved.
Section 4.5.4. Factoring into Primes
Exercises from TAOCP Volume 2 Section 4.5.4: 46/46 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | [10] | simple | verified | 1m11s |
| 2 | [15] | simple | verified | 2m32s |
| 3 | [M20] | math-medium | verified | 7m54s |
| 4 | [M29] | math-hard | solved | 12m58s |
| 5 | [21] | medium | solved | 7m10s |
| 6 | [M24] | math-medium | solved | 7m20s |
| 7 | [25] | medium | verified | 1m45s |
| 8 | ▶ [23] | medium | verified | 1m52s |
| 9 | [M25] | math-medium | verified | 2m28s |
| 10 | ▶ [M26] | math-hard | verified | 7m14s |
| 11 | [M20] | math-medium | verified | 3m01s |
| 12 | [HM25] | hm-medium | solved | 6m29s |
| 14 | [M20] | math-medium | verified | 5m52s |
| 15 | ▶ [M34] | math-hard | verified | 3m40s |
| 16 | [M50] | math-research | verified | 4m51s |
| 17 | [M25] | math-medium | verified | 2m06s |
| 18 | [HM23] | hm-medium | verified | 5m43s |
| 19 | ▶ [M25] | math-medium | verified | 6m08s |
| 20 | [M46] | math-research | verified | 10m38s |
| 21 | [M29] | math-hard | verified | 12m09s |
| 22 | ▶ [M30] | math-hard | verified | 3m19s |
| 23 | [M35] | math-hard | verified | 5m06s |
| 24 | ▶ [**] | verified | 6m49s | |
| 25 | [**] | solved | 10m20s | |
| 26 | ▶ [**] | verified | 7m09s | |
| 27 | ▶ [**] | verified | 6m16s | |
| 28 | [**] | verified | 2m17s | |
| 29 | [**] | verified | 9m44s | |
| 30 | [**] | verified | 2m11s | |
| 31 | [M20] | math-medium | solved | 5m34s |
| 32 | ▶ [M21] | math-medium | verified | 5m40s |
| 33 | [M50] | math-research | verified | 2m55s |
| 34 | [M30] | math-hard | solved | 2m25s |
| 35 | ▶ [M25] | math-medium | verified | 9m49s |
| 36 | [HM24] | hm-medium | verified | 8m47s |
| 37 | [M27] | math-hard | verified | 8m08s |
| 38 | [25] | medium | solved | 9m14s |
| 39 | [40] | project | solved | 11m42s |
| 40 | ▶ [M36] | math-project | verified | 9m30s |
| 41 | [M28] | math-hard | solved | 7m46s |
| 42 | [M35] | math-hard | verified | 6m16s |
| 43 | ▶ [M35] | math-hard | verified | 3m37s |
| 44 | [M35] | math-hard | verified | 12m11s |
| 45 | ▶ [M41] | math-project | verified | 2m11s |
| 46 | [HM30] | hm-hard | verified | 2m23s |
| 47 | [M50] | math-research | verified | 5m35s |
TAOCP 4.5.4 Exercise 1
If $d_k$ is not prime, then $d_k$ has a prime factor $p < d_k$.
TAOCP 4.5.4 Exercise 2
No.
TAOCP 4.5.4 Exercise 3
Let P=\prod_{p\le 1000} p, where the product extends over all prime numbers not exceeding $1000$.
TAOCP 4.5.4 Exercise 4
**Problem:** In the notation of Exercise 3.
TAOCP 4.5.4 Exercise 5
Let N=11111.
TAOCP 4.5.4 Exercise 6
Let $p$ be an odd prime, and let $N$ be an integer such that $p \nmid N$.
TAOCP 4.5.4 Exercise 7
Algorithm D uses, for each modulus $m_i$, a table that indicates whether a residue class modulo $m_i$ can occur as a quadratic residue.
TAOCP 4.5.4 Exercise 8
We wish to transform the classical sieve of Eratosthenes into a form suitable for efficient computation, avoiding multiplications.
TAOCP 4.5.4 Exercise 9
Let $n$ be an odd integer with $n \ge 3$, and let $\lambda(n)$ be the Carmichael function of $n$, as defined in Theorem 3.
TAOCP 4.5.4 Exercise 10
Assume that for every prime divisor $p$ of $n-1$ there exists an integer $x_p$ such that x_p^{(n-1)/p}\equiv 1 \pmod n, \qquad x_p^{\,n-1}\not\equiv 1 \pmod n.
TAOCP 4.5.4 Exercise 11
Algorithm E is the continued-fraction factoring method applied to $\sqrt{kN}$.
TAOCP 4.5.4 Exercise 12
Let N=p_1p_2\cdots p_d have $d$ distinct prime factors.
TAOCP 4.5.4 Exercise 14
Let $T$ be the integer formed in step E3 of Algorithm E.
TAOCP 4.5.4 Exercise 15
Let $P$ and $Q$ be integers with $\gcd(P, Q) = 1$, and define the Lucas sequence $(U_n)$ by $U_0 = 0, \quad U_1 = 1, \quad U_{n+1} = P U_n - Q U_{n-1} \text{ for } n \ge 1.$ Let $N$ be a positive inte...
TAOCP 4.5.4 Exercise 16
A _Mersenne number_ is a number of the form $M_p = 2^p - 1,$ where $p$ is a positive integer.
TAOCP 4.5.4 Exercise 17
We prove simultaneously, by induction on the height of the tree, that for every node $(q,x)$: 1.
TAOCP 4.5.4 Exercise 18
Let $N$ be a positive integer with prime factorization N = p_1 p_2 \cdots p_t, \qquad p_1 \le p_2 \le \cdots \le p_t.
TAOCP 4.5.4 Exercise 19
Let D=\prod_{q\le B} q^{e_q}, where $q^{e_q}$ is the largest power of the prime $q$ not exceeding the prescribed bound (later $B=10^5$).
TAOCP 4.5.4 Exercise 20
**Exercise 4.
TAOCP 4.5.4 Exercise 21
The previous argument fails because it interprets $m(p)$ as the number of repeated divisions by $p$ after the algorithm has already reached the trial divisor $p$.
TAOCP 4.5.4 Exercise 22
Let $n\ge 3$ be an odd integer.
TAOCP 4.5.4 Exercise 23
For odd integers $q>1$, the Jacobi symbol is defined by \left(\frac{p}{q}\right)\in\{-1,0,1\}, with
TAOCP 4.5.4 Exercise 24
**Solution.
TAOCP 4.5.4 Exercise 25
**Exercise 4.
TAOCP 4.5.4 Exercise 26
**Solution.
TAOCP 4.5.4 Exercise 27
**Solution.
TAOCP 4.5.4 Exercise 28
Let $v_p(n)$ denote the exponent of $p$ in $n$.
TAOCP 4.5.4 Exercise 29
**Solution to Exercise 4.
TAOCP 4.5.4 Exercise 30
Let S=\{(e_1,\ldots,e_m): e_1+\cdots+e_m\le r/2\}.
TAOCP 4.5.4 Exercise 31
Let $P_k$ denote the probability that the first $k$ parity vectors produced by Dixon's algorithm are linearly independent in $GF(2)^m$, under the usual heuristic assumption that the vectors are indepe...
TAOCP 4.5.4 Exercise 32
In textbook RSA, a message $M$ is encoded as C \equiv M^3 \pmod N, where $N=pq$ and the public exponent is $3$.
TAOCP 4.5.4 Exercise 33
Let $N = pq$ be a product of two distinct primes $p$ and $q$ such that $p \equiv q \equiv 2 \pmod{3}.$ Suppose we are given an integer $y \equiv x^3 \pmod{N}$ and assume the existence of a "reasonably...
TAOCP 4.5.4 Exercise 34
Let N=pq, where $p$ and $q$ are the RSA primes.
TAOCP 4.5.4 Exercise 35
Let N = pq, \qquad p \equiv 3 \pmod 8, \qquad q \equiv 7 \pmod 8 be the product of two distinct odd primes.
TAOCP 4.5.4 Exercise 36
The reviewer's criticism is misplaced in one essential respect: it evaluates the submission as though the missing information were available.
TAOCP 4.5.4 Exercise 37
Let \sqrt D=[R;\overline{a_1,a_2,\ldots,a_m}], \qquad R=\lfloor \sqrt D\rfloor , where $D$ is not a perfect square.
TAOCP 4.5.4 Exercise 38
The exercise is inherently computational.
TAOCP 4.5.4 Exercise 39
**Problem restated.
TAOCP 4.5.4 Exercise 40
The machine performs addition, subtraction, multiplication, integer division, and equality tests on arbitrarily large integers in unit time.
TAOCP 4.5.4 Exercise 41
Let $N$ be a positive integer.
TAOCP 4.5.4 Exercise 42
Let D=\{\,d:d\mid N,\ d\equiv r \pmod s\,\}, where
TAOCP 4.5.4 Exercise 43
Let m=pq, where $p\equiv q\equiv3\pmod4$, and let $Q_m$ denote the set of quadratic residues modulo $m$ whose unique square roots also lie in $Q_m$.
TAOCP 4.5.4 Exercise 44
Let f(X) = a_0 + a_1 X + a_2 X^2 + a_3 X^3 and suppose we are given integers $m_1, \dots, m_7 > 10^{72}$ that are pairwise coprime, with
TAOCP 4.5.4 Exercise 45
Given odd $n$ with $\gcd(ab,n)=1$, we seek an efficient algorithm that finds integers $x,y$ satisfying x^2-ay^2\equiv b \pmod n, without knowing the factorization of $n$.