Book a Demo!
CoCalc Logo Icon
StoreFeaturesDocsShareSupportNewsAboutPoliciesSign UpSign In
Download

📚 The CoCalc Library - books, templates and other resources

133948 views
License: OTHER
Tweet
Share
Share
Kernel: 
%%html
<link href="http://mathbook.pugetsound.edu/beta/mathbook-content.css" rel="stylesheet" type="text/css" />
<link href="https://aimath.org/mathbook/mathbook-add-on.css" rel="stylesheet" type="text/css" />
<style>.subtitle {font-size:medium; display:block}</style>
<link href="https://fonts.googleapis.com/css?family=Open+Sans:400,400italic,600,600italic" rel="stylesheet" type="text/css" />
<link href="https://fonts.googleapis.com/css?family=Inconsolata:400,700&subset=latin,latin-ext" rel="stylesheet" type="text/css" /><!-- Hide this cell. -->
<script>
var cell = $(".container .cell").eq(0), ia = cell.find(".input_area")
if (cell.find(".toggle-button").length == 0) {
ia.after(
    $('<button class="toggle-button">Toggle hidden code</button>').click(
        function (){ ia.toggle() }
        )
    )
ia.hide()
}
</script>

Important: to view this notebook properly you will need to execute the cell above, which assumes you have an Internet connection. It should already be selected, or place your cursor anywhere above to select. Then press the "Run" button in the menu bar above (the right-pointing arrowhead), or press Shift-Enter on your keyboard.

ParseError: KaTeX parse error: \newcommand{\lt} attempting to redefine \lt; use \renewcommand

Section7.4Additional Exercises: Primality and Factoring

¶

In the RSA cryptosystem it is important to be able to find large prime numbers easily. Also, this cryptosystem is not secure if we can factor a composite number that is the product of two large primes. The solutions to both of these problems are quite easy. To find out if a number $n$ is prime or to factor $n\text{,}$ we can use trial division. We simply divide $n$ by $d = 2, 3, \ldots, \sqrt{n}\text{.}$ Either a factorization will be obtained, or $n$ is prime if no $d$ divides $n\text{.}$ The problem is that such a computation is prohibitively time-consuming if $n$ is very large.

1

A better algorithm for factoring odd positive integers is .

  1. Let $n= ab$ be an odd composite number. Prove that $n$ can be written as the difference of two perfect squares:

    \begin{equation*} n = x^2 - y^2 = (x - y)(x + y). \end{equation*}

    Consequently, a positive odd integer can be factored exactly when we can find integers $x$ and $y$ such that $n = x^2 - y^2\text{.}$

  2. Write a program to implement the following factorization algorithm based on the observation in part (a). The expression ceiling(sqrt(n)) means the smallest integer greater than or equal to the square root of $n\text{.}$ Write another program to do factorization using trial division and compare the speed of the two algorithms. Which algorithm is faster and why?

x := ceiling(sqrt(n))
y := 1

1 : while x^2 - y^2 > n do y := y + 1

if x^2 - y^2 < n then x := x + 1 y := 1 goto 1 else if x^2 - y^2 = 0 then a := x - y b := x + y write n = a * b

2Primality Testing

Recall Fermat's Little Theorem from Chapter 6. Let $p$ be prime with $\gcd(a, p) = 1\text{.}$ Then $a^{p-1} \equiv 1 \pmod{p}\text{.}$ We can use Fermat's Little Theorem as a screening test for primes. For example, 15 cannot be prime since

\begin{equation*} 2^{15-1} \equiv 2^{14} \equiv 4 \pmod{15}. \end{equation*}

However, 17 is a potential prime since

\begin{equation*} 2^{17-1} \equiv 2^{16} \equiv 1 \pmod{17}. \end{equation*}

We say that an odd composite number $n$ is a if

\begin{equation*} 2^{n-1} \equiv 1 \pmod{n}. \end{equation*}

Which of the following numbers are primes and which are pseudoprimes?

  1. 342

  2. 811

  3. 601

  4. 561

  5. 771

  6. 631

3

Let $n$ be an odd composite number and $b$ be a positive integer such that $\gcd(b, n) = 1\text{.}$ If $b^{n-1} \equiv 1 \pmod{n}\text{,}$ then $n$ is a $b\text{.}$ Show that 341 is a pseudoprime base 2 but not a pseudoprime base 3.

4

Write a program to determine all primes less than 2000 using trial division. Write a second program that will determine all numbers less than 2000 that are either primes or pseudoprimes. Compare the speed of the two programs. How many pseudoprimes are there below 2000?

There exist composite numbers that are pseudoprimes for all bases to which they are relatively prime. These numbers are called . The first Carmichael number is $561 = 3 \cdot 11 \cdot 17\text{.}$ In 1992, Alford, Granville, and Pomerance proved that there are an infinite number of Carmichael numbers [4]. However, Carmichael numbers are very rare. There are only $2163$ Carmichael numbers less than $25 \times 10^9\text{.}$ For more sophisticated primality tests, see [1], [6], or [7].