{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Computing Jacobi symbols\n", "\n", "We use the function `jacobi` to compute the Jacobi symbols for the given numbers." ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "from algorithms.modular import jacobi" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "7411 9283 1\n", "\t9283 mod 8 = 3\n", "\t7411 mod 4 = 3\n", "\t9283 mod 4 = 3\n", "9283 7411 -1\n", "1872 7411 -1\n", "\t7411 mod 8 = 3\n", "936 7411 1\n", "468 7411 -1\n", "234 7411 1\n", "117 7411 -1\n", "\t117 mod 4 = 1\n", "\t7411 mod 4 = 3\n", "7411 117 -1\n", "40 117 -1\n", "\t117 mod 8 = 5\n", "20 117 1\n", "10 117 -1\n", "5 117 1\n", "\t5 mod 4 = 1\n", "\t117 mod 4 = 1\n", "117 5 1\n", "2 5 1\n", "\t5 mod 8 = 5\n", "1 5 -1\n" ] }, { "data": { "text/plain": [ "-1" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "jacobi(7411, 9283, trace=True)" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "1094 1987 1\n", "\t1987 mod 8 = 3\n", "547 1987 -1\n", "\t547 mod 4 = 3\n", "\t1987 mod 4 = 3\n", "1987 547 1\n", "346 547 1\n", "\t547 mod 8 = 3\n", "173 547 -1\n", "\t173 mod 4 = 1\n", "\t547 mod 4 = 3\n", "547 173 -1\n", "28 173 -1\n", "\t173 mod 8 = 5\n", "14 173 1\n", "7 173 -1\n", "\t7 mod 4 = 3\n", "\t173 mod 4 = 1\n", "173 7 -1\n", "5 7 -1\n", "\t7 mod 8 = 7\n", "\t5 mod 4 = 1\n", "\t7 mod 4 = 3\n", "7 5 -1\n", "2 5 -1\n", "\t5 mod 8 = 5\n", "1 5 1\n" ] }, { "data": { "text/plain": [ "1" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "jacobi(20964, 1987, trace=True)" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "1234567 11111111 1\n", "\t11111111 mod 8 = 7\n", "\t1234567 mod 4 = 3\n", "\t11111111 mod 4 = 3\n", "11111111 1234567 -1\n", "8 1234567 -1\n", "\t1234567 mod 8 = 7\n", "4 1234567 -1\n", "2 1234567 -1\n", "1 1234567 -1\n" ] }, { "data": { "text/plain": [ "-1" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "jacobi(1234567, 11111111, trace=True)" ] } ], "metadata": { "kernelspec": { "display_name": "SageMath 9.2.rc2", "language": "sage", "name": "sagemath" }, "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.8.5" } }, "nbformat": 4, "nbformat_minor": 4 }