def create_elliptic_multiplication_table(modulus=17):
    """
    Створює таблицю множення за модулем для еліптичних кривих
    """
    print(f"=== ТАБЛИЦЯ МНОЖЕННЯ ЗА МОДУЛЕМ {modulus} ===\n")
 
    # Заголовок таблиці
    header = "   | " + " ".join(f"{i:2d}" for i in range(modulus))
    print(header)
    print("---+" + "-" * (3 * modulus))
 
    # Тіло таблиці
    for i in range(modulus):
        row = f"{i:2d} | "
        for j in range(modulus):
            result = (i * j) % modulus
            row += f"{result:2d} "
        print(row)
 
def show_modular_inverses(modulus=17):
    """
    Показує обернені елементи за модулем
    """
    print(f"\n=== ОБЕРНЕНІ ЕЛЕМЕНТИ ЗА МОДУЛЕМ {modulus} ===")
    print("(числа, які при множенні дають 1)")
 
    inverses = []
    for i in range(1, modulus):
        for j in range(1, modulus):
            if (i * j) % modulus == 1:
                inverses.append((i, j))
                print(f"{i}⁻¹ = {j}  (бо {i} × {j} = {i*j} ≡ {i*j % modulus} mod {modulus})")
                break
 
def elliptic_curve_points(a, b, p):
    """
    Знаходить точки на еліптичній кривій y² = x³ + ax + b (mod p)
    """
    print(f"\n=== ТОЧКИ НА КРИВІЙ y² = x³ + {a}x + {b} (mod {p}) ===")
 
    points = []
    for x in range(p):
        # Обчислюємо праву частину: x³ + ax + b
        rhs = (x*x*x + a*x + b) % p
 
        # Шукаємо y такі, що y² ≡ rhs (mod p)
        for y in range(p):
            if (y*y) % p == rhs:
                points.append((x, y))
                print(f"  ({x}, {y})")
 
    print(f"Всього точок: {len(points)}")
    return points
 
def show_elliptic_addition():
    """
    Демонструє додавання точок на еліптичній кривій
    """
    print("\n=== ДОДАВАННЯ ТОЧОК НА ЕЛІПТИЧНІЙ КРИВІЙ ===")
    print("P + Q = R, де:")
    print("- Проводимо пряму через P та Q")
    print("- Знаходимо третю точку перетину з кривою")
    print("- Відображаємо відносно осі X")
 
    # Простий приклад
    print("\nПриклад на кривій y² = x³ + 2x + 3 (mod 17):")
    print("Якщо P = (1, 6) і Q = (3, 1):")
    print("P + Q = (16, 13)")
 
def main():
    print("=" * 60)
    print("МАТЕМАТИКА ЕЛІПТИЧНИХ КРИВИХ - ТАБЛИЦІ МНОЖЕННЯ")
    print("=" * 60)
 
    # Основна таблиця множення за модулем
    create_elliptic_multiplication_table(17)
 
    # Обернені елементи
    show_modular_inverses(17)
 
    # Приклади еліптичних кривих
    print("\n" + "=" * 60)
    print("ПРИКЛАДИ ЕЛІПТИЧНИХ КРИВИХ")
    print("=" * 60)
 
    # Крива 1
    points1 = elliptic_curve_points(2, 3, 17)
 
    # Крива 2
    points2 = elliptic_curve_points(1, 1, 17)
 
    # Додавання точок
    show_elliptic_addition()
 
    # Групові операції
    print("\n=== ВЛАСТИВОСТІ ГРУПИ ===")
    print("1. Замкнутість: P + Q завжди на кривій")
    print("2. Асоціативність: (P + Q) + R = P + (Q + R)")
    print("3. Нейтральний елемент: точка на нескінченності O")
    print("4. Обернений елемент: -P = (x, -y)")
 
    # Практичне застосування
    print("\n=== ЗАСТОСУВАННЯ ===")
    print("• Криптографія (ECDSA, ECDH)")
    print("• Цифрові підписи")
    print("• Обмін ключами")
 
if __name__ == "__main__":
    main()

ZGVmIGNyZWF0ZV9lbGxpcHRpY19tdWx0aXBsaWNhdGlvbl90YWJsZShtb2R1bHVzPTE3KToKICAgICIiIgogICAg0KHRgtCy0L7RgNGO0ZQg0YLQsNCx0LvQuNGG0Y4g0LzQvdC+0LbQtdC90L3RjyDQt9CwINC80L7QtNGD0LvQtdC8INC00LvRjyDQtdC70ZbQv9GC0LjRh9C90LjRhSDQutGA0LjQstC40YUKICAgICIiIgogICAgcHJpbnQoZiI9PT0g0KLQkNCR0JvQmNCm0K8g0JzQndCe0JbQldCd0J3QryDQl9CQINCc0J7QlNCj0JvQldCcIHttb2R1bHVzfSA9PT1cbiIpCiAgICAKICAgICMg0JfQsNCz0L7Qu9C+0LLQvtC6INGC0LDQsdC70LjRhtGWCiAgICBoZWFkZXIgPSAiICAgfCAiICsgIiAiLmpvaW4oZiJ7aToyZH0iIGZvciBpIGluIHJhbmdlKG1vZHVsdXMpKQogICAgcHJpbnQoaGVhZGVyKQogICAgcHJpbnQoIi0tLSsiICsgIi0iICogKDMgKiBtb2R1bHVzKSkKICAgIAogICAgIyDQotGW0LvQviDRgtCw0LHQu9C40YbRlgogICAgZm9yIGkgaW4gcmFuZ2UobW9kdWx1cyk6CiAgICAgICAgcm93ID0gZiJ7aToyZH0gfCAiCiAgICAgICAgZm9yIGogaW4gcmFuZ2UobW9kdWx1cyk6CiAgICAgICAgICAgIHJlc3VsdCA9IChpICogaikgJSBtb2R1bHVzCiAgICAgICAgICAgIHJvdyArPSBmIntyZXN1bHQ6MmR9ICIKICAgICAgICBwcmludChyb3cpCgpkZWYgc2hvd19tb2R1bGFyX2ludmVyc2VzKG1vZHVsdXM9MTcpOgogICAgIiIiCiAgICDQn9C+0LrQsNC30YPRlCDQvtCx0LXRgNC90LXQvdGWINC10LvQtdC80LXQvdGC0Lgg0LfQsCDQvNC+0LTRg9C70LXQvAogICAgIiIiCiAgICBwcmludChmIlxuPT09INCe0JHQldCg0J3QldCd0IYg0JXQm9CV0JzQldCd0KLQmCDQl9CQINCc0J7QlNCj0JvQldCcIHttb2R1bHVzfSA9PT0iKQogICAgcHJpbnQoIijRh9C40YHQu9CwLCDRj9C60ZYg0L/RgNC4INC80L3QvtC20LXQvdC90ZYg0LTQsNGO0YLRjCAxKSIpCiAgICAKICAgIGludmVyc2VzID0gW10KICAgIGZvciBpIGluIHJhbmdlKDEsIG1vZHVsdXMpOgogICAgICAgIGZvciBqIGluIHJhbmdlKDEsIG1vZHVsdXMpOgogICAgICAgICAgICBpZiAoaSAqIGopICUgbW9kdWx1cyA9PSAxOgogICAgICAgICAgICAgICAgaW52ZXJzZXMuYXBwZW5kKChpLCBqKSkKICAgICAgICAgICAgICAgIHByaW50KGYie2l94oG7wrkgPSB7an0gICjQsdC+IHtpfSDDlyB7an0gPSB7aSpqfSDiiaEge2kqaiAlIG1vZHVsdXN9IG1vZCB7bW9kdWx1c30pIikKICAgICAgICAgICAgICAgIGJyZWFrCgpkZWYgZWxsaXB0aWNfY3VydmVfcG9pbnRzKGEsIGIsIHApOgogICAgIiIiCiAgICDQl9C90LDRhdC+0LTQuNGC0Ywg0YLQvtGH0LrQuCDQvdCwINC10LvRltC/0YLQuNGH0L3RltC5INC60YDQuNCy0ZbQuSB5wrIgPSB4wrMgKyBheCArIGIgKG1vZCBwKQogICAgIiIiCiAgICBwcmludChmIlxuPT09INCi0J7Qp9Ca0Jgg0J3QkCDQmtCg0JjQktCG0JkgecKyID0geMKzICsge2F9eCArIHtifSAobW9kIHtwfSkgPT09IikKICAgIAogICAgcG9pbnRzID0gW10KICAgIGZvciB4IGluIHJhbmdlKHApOgogICAgICAgICMg0J7QsdGH0LjRgdC70Y7RlNC80L4g0L/RgNCw0LLRgyDRh9Cw0YHRgtC40L3RgzogeMKzICsgYXggKyBiCiAgICAgICAgcmhzID0gKHgqeCp4ICsgYSp4ICsgYikgJSBwCiAgICAgICAgCiAgICAgICAgIyDQqNGD0LrQsNGU0LzQviB5INGC0LDQutGWLCDRidC+IHnCsiDiiaEgcmhzIChtb2QgcCkKICAgICAgICBmb3IgeSBpbiByYW5nZShwKToKICAgICAgICAgICAgaWYgKHkqeSkgJSBwID09IHJoczoKICAgICAgICAgICAgICAgIHBvaW50cy5hcHBlbmQoKHgsIHkpKQogICAgICAgICAgICAgICAgcHJpbnQoZiIgICh7eH0sIHt5fSkiKQogICAgCiAgICBwcmludChmItCS0YHRjNC+0LPQviDRgtC+0YfQvtC6OiB7bGVuKHBvaW50cyl9IikKICAgIHJldHVybiBwb2ludHMKCmRlZiBzaG93X2VsbGlwdGljX2FkZGl0aW9uKCk6CiAgICAiIiIKICAgINCU0LXQvNC+0L3RgdGC0YDRg9GUINC00L7QtNCw0LLQsNC90L3RjyDRgtC+0YfQvtC6INC90LAg0LXQu9GW0L/RgtC40YfQvdGW0Lkg0LrRgNC40LLRltC5CiAgICAiIiIKICAgIHByaW50KCJcbj09PSDQlNCe0JTQkNCS0JDQndCd0K8g0KLQntCn0J7QmiDQndCQINCV0JvQhtCf0KLQmNCn0J3QhtCZINCa0KDQmNCS0IbQmSA9PT0iKQogICAgcHJpbnQoIlAgKyBRID0gUiwg0LTQtToiKQogICAgcHJpbnQoIi0g0J/RgNC+0LLQvtC00LjQvNC+INC/0YDRj9C80YMg0YfQtdGA0LXQtyBQINGC0LAgUSIpCiAgICBwcmludCgiLSDQl9C90LDRhdC+0LTQuNC80L4g0YLRgNC10YLRjiDRgtC+0YfQutGDINC/0LXRgNC10YLQuNC90YMg0Lcg0LrRgNC40LLQvtGOIikKICAgIHByaW50KCItINCS0ZbQtNC+0LHRgNCw0LbQsNGU0LzQviDQstGW0LTQvdC+0YHQvdC+INC+0YHRliBYIikKICAgIAogICAgIyDQn9GA0L7RgdGC0LjQuSDQv9GA0LjQutC70LDQtAogICAgcHJpbnQoIlxu0J/RgNC40LrQu9Cw0LQg0L3QsCDQutGA0LjQstGW0LkgecKyID0geMKzICsgMnggKyAzIChtb2QgMTcpOiIpCiAgICBwcmludCgi0K/QutGJ0L4gUCA9ICgxLCA2KSDRliBRID0gKDMsIDEpOiIpCiAgICBwcmludCgiUCArIFEgPSAoMTYsIDEzKSIpCgpkZWYgbWFpbigpOgogICAgcHJpbnQoIj0iICogNjApCiAgICBwcmludCgi0JzQkNCi0JXQnNCQ0KLQmNCa0JAg0JXQm9CG0J/QotCY0KfQndCY0KUg0JrQoNCY0JLQmNClIC0g0KLQkNCR0JvQmNCm0IYg0JzQndCe0JbQldCd0J3QryIpCiAgICBwcmludCgiPSIgKiA2MCkKICAgIAogICAgIyDQntGB0L3QvtCy0L3QsCDRgtCw0LHQu9C40YbRjyDQvNC90L7QttC10L3QvdGPINC30LAg0LzQvtC00YPQu9C10LwKICAgIGNyZWF0ZV9lbGxpcHRpY19tdWx0aXBsaWNhdGlvbl90YWJsZSgxNykKICAgIAogICAgIyDQntCx0LXRgNC90LXQvdGWINC10LvQtdC80LXQvdGC0LgKICAgIHNob3dfbW9kdWxhcl9pbnZlcnNlcygxNykKICAgIAogICAgIyDQn9GA0LjQutC70LDQtNC4INC10LvRltC/0YLQuNGH0L3QuNGFINC60YDQuNCy0LjRhQogICAgcHJpbnQoIlxuIiArICI9IiAqIDYwKQogICAgcHJpbnQoItCf0KDQmNCa0JvQkNCU0Jgg0JXQm9CG0J/QotCY0KfQndCY0KUg0JrQoNCY0JLQmNClIikKICAgIHByaW50KCI9IiAqIDYwKQogICAgCiAgICAjINCa0YDQuNCy0LAgMQogICAgcG9pbnRzMSA9IGVsbGlwdGljX2N1cnZlX3BvaW50cygyLCAzLCAxNykKICAgIAogICAgIyDQmtGA0LjQstCwIDIKICAgIHBvaW50czIgPSBlbGxpcHRpY19jdXJ2ZV9wb2ludHMoMSwgMSwgMTcpCiAgICAKICAgICMg0JTQvtC00LDQstCw0L3QvdGPINGC0L7Rh9C+0LoKICAgIHNob3dfZWxsaXB0aWNfYWRkaXRpb24oKQogICAgCiAgICAjINCT0YDRg9C/0L7QstGWINC+0L/QtdGA0LDRhtGW0ZcKICAgIHByaW50KCJcbj09PSDQktCb0JDQodCi0JjQktCe0KHQotCGINCT0KDQo9Cf0JggPT09IikKICAgIHByaW50KCIxLiDQl9Cw0LzQutC90YPRgtGW0YHRgtGMOiBQICsgUSDQt9Cw0LLQttC00Lgg0L3QsCDQutGA0LjQstGW0LkiKQogICAgcHJpbnQoIjIuINCQ0YHQvtGG0ZbQsNGC0LjQstC90ZbRgdGC0Yw6IChQICsgUSkgKyBSID0gUCArIChRICsgUikiKQogICAgcHJpbnQoIjMuINCd0LXQudGC0YDQsNC70YzQvdC40Lkg0LXQu9C10LzQtdC90YI6INGC0L7Rh9C60LAg0L3QsCDQvdC10YHQutGW0L3Rh9C10L3QvdC+0YHRgtGWIE8iKQogICAgcHJpbnQoIjQuINCe0LHQtdGA0L3QtdC90LjQuSDQtdC70LXQvNC10L3RgjogLVAgPSAoeCwgLXkpIikKICAgIAogICAgIyDQn9GA0LDQutGC0LjRh9C90LUg0LfQsNGB0YLQvtGB0YPQstCw0L3QvdGPCiAgICBwcmludCgiXG49PT0g0JfQkNCh0KLQntCh0KPQktCQ0J3QndCvID09PSIpCiAgICBwcmludCgi4oCiINCa0YDQuNC/0YLQvtCz0YDQsNGE0ZbRjyAoRUNEU0EsIEVDREgpIikKICAgIHByaW50KCLigKIg0KbQuNGE0YDQvtCy0ZYg0L/RltC00L/QuNGB0LgiKQogICAgcHJpbnQoIuKAoiDQntCx0LzRltC9INC60LvRjtGH0LDQvNC4IikKCmlmIF9fbmFtZV9fID09ICJfX21haW5fXyI6CiAgICBtYWluKCk=