{
"cells": [
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"ExecuteTime": {
"end_time": "2021-04-18T10:42:36.285247Z",
"start_time": "2021-04-18T10:42:36.267236Z"
}
},
"outputs": [],
"source": [
"from Crypto.Util.number import inverse, GCD, isPrime, getPrime"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Prerequisites"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"- Number theory basics"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Theory"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"- https://en.wikipedia.org/wiki/Primality_test"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Probabilistic primality tests"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"- methods by which arbitrary positive integers are tested to provide **partial information** regarding their primality. \n",
"\n",
"How do they work?\n",
"For each odd positive integern,a set $W(n)⊂\\mathbb{Z}_n$ is defined such that the following properties hold:\n",
"1. given $a∈\\mathbb{Z}_n$, it can be checked in deterministic polynomial time whether $a∈W(n)$;\n",
"2. if $n$ is prime, then $W(n)=∅$(the empty set)\n",
"3. if $n$ is composite, then $|W(n)|≥\\dfrac n 2$.\n",
"\n",
"**Def**\n",
"- If $n$ is composite, the elements of $W(n)$are called **witnesses** to the compositeness of $n$, and the elements of the complementary set $L(n)=\\mathbb{Z}_n−W(n)$ are called **liars**\n",
"\n",
"**Framework**:\n",
"- Choose a random $a\\in \\mathbb{Z}_n$\n",
"- Check if $a \\in W(n)$\n",
"- If $a \\in W(n)$\n",
" - return composite (the test is failed with respect to base $a$ => $n$ is **certain** to be composite\n",
"- Else\n",
" - return prime (the test is passed with respect to base $a$) => no conclusion can be drawn => $n$ is **probably prime**\n",
" \n",
"**Remark**:\n",
"- The more tests if passes the higher the probability our probable prime has to be prime\n",
"- We trade computing time for a better approximation of our probable prime"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Fermat's test"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"- https://en.wikipedia.org/wiki/Fermat_primality_test"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Fermat's theorem**:\n",
"- Let $p$ be a prime number and $a$ be an integer not divisible by $p$. Then $a^{p-1} - 1$ is always divisible by $p$, or $a^{p-1} \\equiv 1 \\pmod{p}$\n",
"\n",
"**Idea**: \n",
"- Use the converse :\n",
" - if for some $a$ not divisible by $n$ we have $a^{n-1} \\not\\equiv 1 \\pmod{n}$, then $n$ is definitely composite\n",
" \n",
"**Algorithm**: \n",
"- input $n>3$,the number to be tested and $k$, the number of tests / a bound\n",
"- Repeat k times:\n",
" - Pick a random $a \\in \\{2, n-2\\}$\n",
" - if $a^{n-1} \\not\\equiv 1 \\bmod n$\n",
" - return composite\n",
" - else\n",
" - continue\n",
"- if no composite is returned then return probably prime\n",
" "
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {
"ExecuteTime": {
"end_time": "2021-04-18T10:42:38.831898Z",
"start_time": "2021-04-18T10:42:38.811882Z"
}
},
"outputs": [],
"source": [
"import random\n",
"\n",
"def fermat_test(n, k):\n",
" for i in range(k):\n",
" a = random.randint(2, n-2)\n",
" #print(a)\n",
" if GCD(a, n)!=1: ##Remark this should return COMPOSITE (since you found a divisor !=1) but to show the flaw we did it this way\n",
" i-=1\n",
" continue\n",
" if pow(a, n-1, n) != 1:\n",
" return 'Composite'\n",
" return 'Probably prime'"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {
"ExecuteTime": {
"end_time": "2021-04-18T10:42:39.116928Z",
"start_time": "2021-04-18T10:42:38.964928Z"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Composite\n",
"Probably prime\n"
]
}
],
"source": [
"print(fermat_test(2403, 12))\n",
"p = getPrime(512)\n",
"print(fermat_test(p, 100))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Flaw"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Carmichael numbers pass the test yet they aren't prime:\n",
"- Let $n$ be a Carmichael number, then $a^{n-1} \\equiv 1 \\bmod n$ for **all** $a$ with $\\gcd(a,n) =1$\n",
"- Therefore the search for composite is the same as a search for its factors\n"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {
"ExecuteTime": {
"end_time": "2021-04-18T10:44:20.180541Z",
"start_time": "2021-04-18T10:44:20.171544Z"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"561 is Probably prime but 561 % 3 = 0\n",
"41041 is Probably prime but 41041 % 11 = 0\n"
]
}
],
"source": [
"print(f\"561 is {fermat_test(561, 100)} but 561 % 3 = {561 % 3}\")\n",
"print(f\"41041 is {fermat_test(41041, 100)} but 41041 % 11 = {41041 % 11}\")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Resources"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"- https://www.youtube.com/watch?v=oUMotDWVLpw\n",
"- https://www.youtube.com/watch?v=jbiaz_aHHUQ"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.9.4"
},
"toc": {
"base_numbering": 1,
"nav_menu": {},
"number_sections": true,
"sideBar": true,
"skip_h1_title": false,
"title_cell": "Table of Contents",
"title_sidebar": "Contents",
"toc_cell": false,
"toc_position": {},
"toc_section_display": true,
"toc_window_display": false
}
},
"nbformat": 4,
"nbformat_minor": 2
}