tests/test_prime.py

# -*- coding: utf-8 -*-
#
#  Copyright 2011 Sybren A. Stüvel <sybren@stuvel.eu>
#
#  Licensed under the Apache License, Version 2.0 (the "License");
#  you may not use this file except in compliance with the License.
#  You may obtain a copy of the License at
#
#      http://www.apache.org/licenses/LICENSE-2.0
#
#  Unless required by applicable law or agreed to in writing, software
#  distributed under the License is distributed on an "AS IS" BASIS,
#  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
#  See the License for the specific language governing permissions and
#  limitations under the License.

"""Tests prime functions."""

import unittest

import rsa.prime


class JacobiTest(unittest.TestCase):
    def test_table_values(self):
        """ Tests table of values for 1<=a<=30, 1<=b<=59, where b is odd"""

        # Construct table of values, where case format is (a, b, jacobi(a, b))
        table_values = [
            (1, 1, 1), (1, 3, 1), (1, 5, 1), (1, 7, 1), (1, 9, 1),
            (1, 11, 1), (1, 13, 1), (1, 15, 1), (1, 17, 1), (1, 19, 1),
            (1, 21, 1), (1, 23, 1), (1, 25, 1), (1, 27, 1), (1, 29, 1),
            (1, 31, 1), (1, 33, 1), (1, 35, 1), (1, 37, 1), (1, 39, 1),
            (1, 41, 1), (1, 43, 1), (1, 45, 1), (1, 47, 1), (1, 49, 1),
            (1, 51, 1), (1, 53, 1), (1, 55, 1), (1, 57, 1), (1, 59, 1),
            (2, 1, 1), (2, 3, -1), (2, 5, -1), (2, 7, 1), (2, 9, 1),
            (2, 11, -1), (2, 13, -1), (2, 15, 1), (2, 17, 1), (2, 19, -1),
            (2, 21, -1), (2, 23, 1), (2, 25, 1), (2, 27, -1), (2, 29, -1),
            (2, 31, 1), (2, 33, 1), (2, 35, -1), (2, 37, -1), (2, 39, 1),
            (2, 41, 1), (2, 43, -1), (2, 45, -1), (2, 47, 1), (2, 49, 1),
            (2, 51, -1), (2, 53, -1), (2, 55, 1), (2, 57, 1), (2, 59, -1),
            (3, 1, 1), (3, 3, 0), (3, 5, -1), (3, 7, -1), (3, 9, 0),
            (3, 11, 1), (3, 13, 1), (3, 15, 0), (3, 17, -1), (3, 19, -1),
            (3, 21, 0), (3, 23, 1), (3, 25, 1), (3, 27, 0), (3, 29, -1),
            (3, 31, -1), (3, 33, 0), (3, 35, 1), (3, 37, 1), (3, 39, 0),
            (3, 41, -1), (3, 43, -1), (3, 45, 0), (3, 47, 1), (3, 49, 1),
            (3, 51, 0), (3, 53, -1), (3, 55, -1), (3, 57, 0), (3, 59, 1),
            (4, 1, 1), (4, 3, 1), (4, 5, 1), (4, 7, 1), (4, 9, 1),
            (4, 11, 1), (4, 13, 1), (4, 15, 1), (4, 17, 1), (4, 19, 1),
            (4, 21, 1), (4, 23, 1), (4, 25, 1), (4, 27, 1), (4, 29, 1),
            (4, 31, 1), (4, 33, 1), (4, 35, 1), (4, 37, 1), (4, 39, 1),
            (4, 41, 1), (4, 43, 1), (4, 45, 1), (4, 47, 1), (4, 49, 1),
            (4, 51, 1), (4, 53, 1), (4, 55, 1), (4, 57, 1), (4, 59, 1),
            (5, 1, 1), (5, 3, -1), (5, 5, 0), (5, 7, -1), (5, 9, 1),
            (5, 11, 1), (5, 13, -1), (5, 15, 0), (5, 17, -1), (5, 19, 1),
            (5, 21, 1), (5, 23, -1), (5, 25, 0), (5, 27, -1), (5, 29, 1),
            (5, 31, 1), (5, 33, -1), (5, 35, 0), (5, 37, -1), (5, 39, 1),
            (5, 41, 1), (5, 43, -1), (5, 45, 0), (5, 47, -1), (5, 49, 1),
            (5, 51, 1), (5, 53, -1), (5, 55, 0), (5, 57, -1), (5, 59, 1),
            (6, 1, 1), (6, 3, 0), (6, 5, 1), (6, 7, -1), (6, 9, 0),
            (6, 11, -1), (6, 13, -1), (6, 15, 0), (6, 17, -1), (6, 19, 1),
            (6, 21, 0), (6, 23, 1), (6, 25, 1), (6, 27, 0), (6, 29, 1),
            (6, 31, -1), (6, 33, 0), (6, 35, -1), (6, 37, -1), (6, 39, 0),
            (6, 41, -1), (6, 43, 1), (6, 45, 0), (6, 47, 1), (6, 49, 1),
            (6, 51, 0), (6, 53, 1), (6, 55, -1), (6, 57, 0), (6, 59, -1),
            (7, 1, 1), (7, 3, 1), (7, 5, -1), (7, 7, 0), (7, 9, 1),
            (7, 11, -1), (7, 13, -1), (7, 15, -1), (7, 17, -1), (7, 19, 1),
            (7, 21, 0), (7, 23, -1), (7, 25, 1), (7, 27, 1), (7, 29, 1),
            (7, 31, 1), (7, 33, -1), (7, 35, 0), (7, 37, 1), (7, 39, -1),
            (7, 41, -1), (7, 43, -1), (7, 45, -1), (7, 47, 1), (7, 49, 0),
            (7, 51, -1), (7, 53, 1), (7, 55, 1), (7, 57, 1), (7, 59, 1),
            (8, 1, 1), (8, 3, -1), (8, 5, -1), (8, 7, 1), (8, 9, 1),
            (8, 11, -1), (8, 13, -1), (8, 15, 1), (8, 17, 1), (8, 19, -1),
            (8, 21, -1), (8, 23, 1), (8, 25, 1), (8, 27, -1), (8, 29, -1),
            (8, 31, 1), (8, 33, 1), (8, 35, -1), (8, 37, -1), (8, 39, 1),
            (8, 41, 1), (8, 43, -1), (8, 45, -1), (8, 47, 1), (8, 49, 1),
            (8, 51, -1), (8, 53, -1), (8, 55, 1), (8, 57, 1), (8, 59, -1),
            (9, 1, 1), (9, 3, 0), (9, 5, 1), (9, 7, 1), (9, 9, 0),
            (9, 11, 1), (9, 13, 1), (9, 15, 0), (9, 17, 1), (9, 19, 1),
            (9, 21, 0), (9, 23, 1), (9, 25, 1), (9, 27, 0), (9, 29, 1),
            (9, 31, 1), (9, 33, 0), (9, 35, 1), (9, 37, 1), (9, 39, 0),
            (9, 41, 1), (9, 43, 1), (9, 45, 0), (9, 47, 1), (9, 49, 1),
            (9, 51, 0), (9, 53, 1), (9, 55, 1), (9, 57, 0), (9, 59, 1),
            (10, 1, 1), (10, 3, 1), (10, 5, 0), (10, 7, -1), (10, 9, 1),
            (10, 11, -1), (10, 13, 1), (10, 15, 0), (10, 17, -1), (10, 19, -1),
            (10, 21, -1), (10, 23, -1), (10, 25, 0), (10, 27, 1), (10, 29, -1),
            (10, 31, 1), (10, 33, -1), (10, 35, 0), (10, 37, 1), (10, 39, 1),
            (10, 41, 1), (10, 43, 1), (10, 45, 0), (10, 47, -1), (10, 49, 1),
            (10, 51, -1), (10, 53, 1), (10, 55, 0), (10, 57, -1), (10, 59, -1),
            (11, 1, 1), (11, 3, -1), (11, 5, 1), (11, 7, 1), (11, 9, 1),
            (11, 11, 0), (11, 13, -1), (11, 15, -1), (11, 17, -1), (11, 19, 1),
            (11, 21, -1), (11, 23, -1), (11, 25, 1), (11, 27, -1), (11, 29, -1),
            (11, 31, -1), (11, 33, 0), (11, 35, 1), (11, 37, 1), (11, 39, 1),
            (11, 41, -1), (11, 43, 1), (11, 45, 1), (11, 47, -1), (11, 49, 1),
            (11, 51, 1), (11, 53, 1), (11, 55, 0), (11, 57, -1), (11, 59, -1),
            (12, 1, 1), (12, 3, 0), (12, 5, -1), (12, 7, -1), (12, 9, 0),
            (12, 11, 1), (12, 13, 1), (12, 15, 0), (12, 17, -1), (12, 19, -1),
            (12, 21, 0), (12, 23, 1), (12, 25, 1), (12, 27, 0), (12, 29, -1),
            (12, 31, -1), (12, 33, 0), (12, 35, 1), (12, 37, 1), (12, 39, 0),
            (12, 41, -1), (12, 43, -1), (12, 45, 0), (12, 47, 1), (12, 49, 1),
            (12, 51, 0), (12, 53, -1), (12, 55, -1), (12, 57, 0), (12, 59, 1),
            (13, 1, 1), (13, 3, 1), (13, 5, -1), (13, 7, -1), (13, 9, 1),
            (13, 11, -1), (13, 13, 0), (13, 15, -1), (13, 17, 1), (13, 19, -1),
            (13, 21, -1), (13, 23, 1), (13, 25, 1), (13, 27, 1), (13, 29, 1),
            (13, 31, -1), (13, 33, -1), (13, 35, 1), (13, 37, -1), (13, 39, 0),
            (13, 41, -1), (13, 43, 1), (13, 45, -1), (13, 47, -1), (13, 49, 1),
            (13, 51, 1), (13, 53, 1), (13, 55, 1), (13, 57, -1), (13, 59, -1),
            (14, 1, 1), (14, 3, -1), (14, 5, 1), (14, 7, 0), (14, 9, 1),
            (14, 11, 1), (14, 13, 1), (14, 15, -1), (14, 17, -1), (14, 19, -1),
            (14, 21, 0), (14, 23, -1), (14, 25, 1), (14, 27, -1), (14, 29, -1),
            (14, 31, 1), (14, 33, -1), (14, 35, 0), (14, 37, -1), (14, 39, -1),
            (14, 41, -1), (14, 43, 1), (14, 45, 1), (14, 47, 1), (14, 49, 0),
            (14, 51, 1), (14, 53, -1), (14, 55, 1), (14, 57, 1), (14, 59, -1),
            (15, 1, 1), (15, 3, 0), (15, 5, 0), (15, 7, 1), (15, 9, 0),
            (15, 11, 1), (15, 13, -1), (15, 15, 0), (15, 17, 1), (15, 19, -1),
            (15, 21, 0), (15, 23, -1), (15, 25, 0), (15, 27, 0), (15, 29, -1),
            (15, 31, -1), (15, 33, 0), (15, 35, 0), (15, 37, -1), (15, 39, 0),
            (15, 41, -1), (15, 43, 1), (15, 45, 0), (15, 47, -1), (15, 49, 1),
            (15, 51, 0), (15, 53, 1), (15, 55, 0), (15, 57, 0), (15, 59, 1),
            (16, 1, 1), (16, 3, 1), (16, 5, 1), (16, 7, 1), (16, 9, 1),
            (16, 11, 1), (16, 13, 1), (16, 15, 1), (16, 17, 1), (16, 19, 1),
            (16, 21, 1), (16, 23, 1), (16, 25, 1), (16, 27, 1), (16, 29, 1),
            (16, 31, 1), (16, 33, 1), (16, 35, 1), (16, 37, 1), (16, 39, 1),
            (16, 41, 1), (16, 43, 1), (16, 45, 1), (16, 47, 1), (16, 49, 1),
            (16, 51, 1), (16, 53, 1), (16, 55, 1), (16, 57, 1), (16, 59, 1),
            (17, 1, 1), (17, 3, -1), (17, 5, -1), (17, 7, -1), (17, 9, 1),
            (17, 11, -1), (17, 13, 1), (17, 15, 1), (17, 17, 0), (17, 19, 1),
            (17, 21, 1), (17, 23, -1), (17, 25, 1), (17, 27, -1), (17, 29, -1),
            (17, 31, -1), (17, 33, 1), (17, 35, 1), (17, 37, -1), (17, 39, -1),
            (17, 41, -1), (17, 43, 1), (17, 45, -1), (17, 47, 1), (17, 49, 1),
            (17, 51, 0), (17, 53, 1), (17, 55, 1), (17, 57, -1), (17, 59, 1),
            (18, 1, 1), (18, 3, 0), (18, 5, -1), (18, 7, 1), (18, 9, 0),
            (18, 11, -1), (18, 13, -1), (18, 15, 0), (18, 17, 1), (18, 19, -1),
            (18, 21, 0), (18, 23, 1), (18, 25, 1), (18, 27, 0), (18, 29, -1),
            (18, 31, 1), (18, 33, 0), (18, 35, -1), (18, 37, -1), (18, 39, 0),
            (18, 41, 1), (18, 43, -1), (18, 45, 0), (18, 47, 1), (18, 49, 1),
            (18, 51, 0), (18, 53, -1), (18, 55, 1), (18, 57, 0), (18, 59, -1),
            (19, 1, 1), (19, 3, 1), (19, 5, 1), (19, 7, -1), (19, 9, 1),
            (19, 11, -1), (19, 13, -1), (19, 15, 1), (19, 17, 1), (19, 19, 0),
            (19, 21, -1), (19, 23, -1), (19, 25, 1), (19, 27, 1), (19, 29, -1),
            (19, 31, 1), (19, 33, -1), (19, 35, -1), (19, 37, -1), (19, 39, -1),
            (19, 41, -1), (19, 43, -1), (19, 45, 1), (19, 47, -1), (19, 49, 1),
            (19, 51, 1), (19, 53, -1), (19, 55, -1), (19, 57, 0), (19, 59, 1),
            (20, 1, 1), (20, 3, -1), (20, 5, 0), (20, 7, -1), (20, 9, 1),
            (20, 11, 1), (20, 13, -1), (20, 15, 0), (20, 17, -1), (20, 19, 1),
            (20, 21, 1), (20, 23, -1), (20, 25, 0), (20, 27, -1), (20, 29, 1),
            (20, 31, 1), (20, 33, -1), (20, 35, 0), (20, 37, -1), (20, 39, 1),
            (20, 41, 1), (20, 43, -1), (20, 45, 0), (20, 47, -1), (20, 49, 1),
            (20, 51, 1), (20, 53, -1), (20, 55, 0), (20, 57, -1), (20, 59, 1),
            (21, 1, 1), (21, 3, 0), (21, 5, 1), (21, 7, 0), (21, 9, 0),
            (21, 11, -1), (21, 13, -1), (21, 15, 0), (21, 17, 1), (21, 19, -1),
            (21, 21, 0), (21, 23, -1), (21, 25, 1), (21, 27, 0), (21, 29, -1),
            (21, 31, -1), (21, 33, 0), (21, 35, 0), (21, 37, 1), (21, 39, 0),
            (21, 41, 1), (21, 43, 1), (21, 45, 0), (21, 47, 1), (21, 49, 0),
            (21, 51, 0), (21, 53, -1), (21, 55, -1), (21, 57, 0), (21, 59, 1),
            (22, 1, 1), (22, 3, 1), (22, 5, -1), (22, 7, 1), (22, 9, 1),
            (22, 11, 0), (22, 13, 1), (22, 15, -1), (22, 17, -1), (22, 19, -1),
            (22, 21, 1), (22, 23, -1), (22, 25, 1), (22, 27, 1), (22, 29, 1),
            (22, 31, -1), (22, 33, 0), (22, 35, -1), (22, 37, -1), (22, 39, 1),
            (22, 41, -1), (22, 43, -1), (22, 45, -1), (22, 47, -1), (22, 49, 1),
            (22, 51, -1), (22, 53, -1), (22, 55, 0), (22, 57, -1), (22, 59, 1),
            (23, 1, 1), (23, 3, -1), (23, 5, -1), (23, 7, 1), (23, 9, 1),
            (23, 11, 1), (23, 13, 1), (23, 15, 1), (23, 17, -1), (23, 19, 1),
            (23, 21, -1), (23, 23, 0), (23, 25, 1), (23, 27, -1), (23, 29, 1),
            (23, 31, -1), (23, 33, -1), (23, 35, -1), (23, 37, -1), (23, 39, -1),
            (23, 41, 1), (23, 43, 1), (23, 45, -1), (23, 47, -1), (23, 49, 1),
            (23, 51, 1), (23, 53, -1), (23, 55, -1), (23, 57, -1), (23, 59, -1),
            (24, 1, 1), (24, 3, 0), (24, 5, 1), (24, 7, -1), (24, 9, 0),
            (24, 11, -1), (24, 13, -1), (24, 15, 0), (24, 17, -1), (24, 19, 1),
            (24, 21, 0), (24, 23, 1), (24, 25, 1), (24, 27, 0), (24, 29, 1),
            (24, 31, -1), (24, 33, 0), (24, 35, -1), (24, 37, -1), (24, 39, 0),
            (24, 41, -1), (24, 43, 1), (24, 45, 0), (24, 47, 1), (24, 49, 1),
            (24, 51, 0), (24, 53, 1), (24, 55, -1), (24, 57, 0), (24, 59, -1),
            (25, 1, 1), (25, 3, 1), (25, 5, 0), (25, 7, 1), (25, 9, 1),
            (25, 11, 1), (25, 13, 1), (25, 15, 0), (25, 17, 1), (25, 19, 1),
            (25, 21, 1), (25, 23, 1), (25, 25, 0), (25, 27, 1), (25, 29, 1),
            (25, 31, 1), (25, 33, 1), (25, 35, 0), (25, 37, 1), (25, 39, 1),
            (25, 41, 1), (25, 43, 1), (25, 45, 0), (25, 47, 1), (25, 49, 1),
            (25, 51, 1), (25, 53, 1), (25, 55, 0), (25, 57, 1), (25, 59, 1),
            (26, 1, 1), (26, 3, -1), (26, 5, 1), (26, 7, -1), (26, 9, 1),
            (26, 11, 1), (26, 13, 0), (26, 15, -1), (26, 17, 1), (26, 19, 1),
            (26, 21, 1), (26, 23, 1), (26, 25, 1), (26, 27, -1), (26, 29, -1),
            (26, 31, -1), (26, 33, -1), (26, 35, -1), (26, 37, 1), (26, 39, 0),
            (26, 41, -1), (26, 43, -1), (26, 45, 1), (26, 47, -1), (26, 49, 1),
            (26, 51, -1), (26, 53, -1), (26, 55, 1), (26, 57, -1), (26, 59, 1),
            (27, 1, 1), (27, 3, 0), (27, 5, -1), (27, 7, -1), (27, 9, 0),
            (27, 11, 1), (27, 13, 1), (27, 15, 0), (27, 17, -1), (27, 19, -1),
            (27, 21, 0), (27, 23, 1), (27, 25, 1), (27, 27, 0), (27, 29, -1),
            (27, 31, -1), (27, 33, 0), (27, 35, 1), (27, 37, 1), (27, 39, 0),
            (27, 41, -1), (27, 43, -1), (27, 45, 0), (27, 47, 1), (27, 49, 1),
            (27, 51, 0), (27, 53, -1), (27, 55, -1), (27, 57, 0), (27, 59, 1),
            (28, 1, 1), (28, 3, 1), (28, 5, -1), (28, 7, 0), (28, 9, 1),
            (28, 11, -1), (28, 13, -1), (28, 15, -1), (28, 17, -1), (28, 19, 1),
            (28, 21, 0), (28, 23, -1), (28, 25, 1), (28, 27, 1), (28, 29, 1),
            (28, 31, 1), (28, 33, -1), (28, 35, 0), (28, 37, 1), (28, 39, -1),
            (28, 41, -1), (28, 43, -1), (28, 45, -1), (28, 47, 1), (28, 49, 0),
            (28, 51, -1), (28, 53, 1), (28, 55, 1), (28, 57, 1), (28, 59, 1),
            (29, 1, 1), (29, 3, -1), (29, 5, 1), (29, 7, 1), (29, 9, 1),
            (29, 11, -1), (29, 13, 1), (29, 15, -1), (29, 17, -1), (29, 19, -1),
            (29, 21, -1), (29, 23, 1), (29, 25, 1), (29, 27, -1), (29, 29, 0),
            (29, 31, -1), (29, 33, 1), (29, 35, 1), (29, 37, -1), (29, 39, -1),
            (29, 41, -1), (29, 43, -1), (29, 45, 1), (29, 47, -1), (29, 49, 1),
            (29, 51, 1), (29, 53, 1), (29, 55, -1), (29, 57, 1), (29, 59, 1),
            (30, 1, 1), (30, 3, 0), (30, 5, 0), (30, 7, 1), (30, 9, 0),
            (30, 11, -1), (30, 13, 1), (30, 15, 0), (30, 17, 1), (30, 19, 1),
            (30, 21, 0), (30, 23, -1), (30, 25, 0), (30, 27, 0), (30, 29, 1),
            (30, 31, -1), (30, 33, 0), (30, 35, 0), (30, 37, 1), (30, 39, 0),
            (30, 41, -1), (30, 43, -1), (30, 45, 0), (30, 47, -1), (30, 49, 1),
            (30, 51, 0), (30, 53, -1), (30, 55, 0), (30, 57, 0), (30, 59, -1),
        ]

        for case in table_values:
            a, b, result = case
            self.assertEqual(rsa.prime.jacobi(a, b), result)