Решение fireshark - EasyMath

Сложность: 2 – Needs a little brain (or luck)
Платформа: Windows
Язык: (Visual) Basic
Дано: EasyMath

Find the right input!

Решение (автор Kostya)
опубликовано 06.04.2012

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
image01.jpg

На самом деле этот crackme не совсем crackme. Его цель: всего лищь найти решение для одного уравнения. Когда мы вводим что-то в поля ввода (как видим на картинке - их два), то в случае ошибки получаем сообщение: “Almost, just a little more careful!” (мол, ищи более тщательно). После небольшого исследования выясняем, что в качестве входных данных выступают только целые числа. Числа с плавающей запятой преобразуются в целые (например, 123,45 в 123). Смотрите:



А здесь происходит проверка входных данных:



Т.е. идет вычисление уравнения:
Х2 = 193 * Y2 + 1
или
Х2 - 193 * Y2 = 1

Чтобы решить это уравнение, надо найти X и Y. Это уравнение Пелля (иногда это уравнение называют неопределенным уравнением Ферма, хотя название "уравнение Пелля" в настоящее время более распространено) - диофантово уравнение второй степени:

(1)
\begin{align} x^2 - n * y^2 = 1 \end{align}

где n - натуральное число, не являющееся полным квадратом

Диофантовы уравнения - в разных областях математики, а в особенности в алгебраической геометрии и теории чисел, встречаются уравнения, обе части которых представляют собой многочлены, а решения требуется найти в целых числах. Такие уравнения называются диофантовыми. Среди диофантовых уравнений встречаются как простые, так и те, решения которых требуют применения современных математических теорий. Примером последних служат знаменитые уравнения Ферма:

(2)
\begin{align} x^n + y^n = z^n, n > 2 \end{align}

которые человечество пыталось решить на протяжении более трёх веков, и лишь несколько лет назад английскому математику Эндрю Уайлсу удалось доказать, что они не имеют решений в целых положительных числах.
В.О.Бугаенко "Уравнения Пелля"


Ниже представлен код для решения уравнения Пелля (методом цепных дробей).

import math
 
def pell(d):
    p,k,x1,y,sd = 1,1,1,0,math.sqrt(d)
 
    while k != 1 or y == 0:
        p = k * (p/k + 1) - p
        p = p - int((p -sd) / k) * k
        x = (p * x1 + d * y) / abs(k)
        y = (p*y + x1)/abs(k)
        k = (p*p - d) / k
 
        x1 = x
 
    return x, y
 
x = 0
y = 0
x,y = pell(193)
print "X = "+str(x)+"  Y = "+str(y)


Решение:
X = 6224323426849 Y = 448036604040

image00.jpg

P.S. А что это за волшебное число 13344720061778?
Смотрим в код и находим решение - (x + y) * 2 = (6224323426849 + 448036604040) * 2 = 13344720061778
Пока не указано иное, содержимое этой страницы распространяется по лицензии Creative Commons Attribution-ShareAlike 3.0 License