?

Log in

No account? Create an account

Previous Entry | Next Entry

Помогите студенту :)

Задачку тут принесли со второго курса. Надо написать программу (под любую среду и библиотеку на выбор, я сходу вспомнил только про bc и gmp :)), которая за максимум 2 минуты вычислит чего за число в степени 137 при делении на 1395667104275780136328137029621666356023102373828208614259008333518048661758896451829091736021396841 даст остаток 853850955301866163689247242586471298622619472656175640289466689838635348038838411985760314991260370.
Чо-та тупым перебором моя программа за 10 минут дошла до 500000 и не нашла. Кто теорию чисел хорошо знает? :)

Tags:

Comments

( 18 comments — Leave a comment )
rblaze
Dec. 20th, 2010 02:46 pm (UTC)
Это они RSA ломают, что ли?
uncle_asa
Dec. 20th, 2010 02:51 pm (UTC)
да не, говорят программирование :)
rblaze
Dec. 20th, 2010 02:59 pm (UTC)
А выглядит в точности как оно: c = m**e mod n
c - остаток от деления, n - делитель, e = 137, m тебе надо найти, а всё вместе RSAproblem и хороших решений не имеет.

Разве что там в числах дырка, но я не настолько хорошо с криптоанализом знаком, чтобы это сходу обнаружить.
uncle_asa
Dec. 20th, 2010 03:05 pm (UTC)
То есть издеваются над студентами? ;)
rblaze
Dec. 20th, 2010 03:08 pm (UTC)
Вообще говоря, да :) Но если всё-таки пробовать, то начать с факторизации делителя, если получится - остальное тривиально.
uncle_asa
Dec. 20th, 2010 03:25 pm (UTC)
Ну по крайней мере оно до 28 700 000 ни на что не делится :) Ну их нафиг :)
andy1618
Feb. 23rd, 2011 02:41 am (UTC)
Да, по-видимому, это препод провоцирует студентов на поиски эффективных алгоритмов криптоанализа RSA.
Длина модуля (100 знаков) - классическая и по современным понятиям небольшая. Пишут, что раскладывается за часы:
http://en.wikipedia.org/wiki/RSA-200#RSA-100

Для решения за 2 минуты нужна какая-то доп. информация. Возможно, условие задачи неполное.
ufm
Dec. 20th, 2010 03:11 pm (UTC)
+1. Т.е. такое ощущение, что в лоб оно не решается по определению.
uncle_asa
Dec. 20th, 2010 03:16 pm (UTC)
Надо спросить у коллеги чего у него там сын ломает ;)
ufm
Dec. 20th, 2010 03:38 pm (UTC)
Но как-то у тебя долго считает. У меня до 500000 меньше чем за минуту добегает. :)
ufm
Dec. 20th, 2010 03:42 pm (UTC)
Посмотрел - первый милион - примерно за минуту. :)
uncle_asa
Dec. 20th, 2010 04:11 pm (UTC)
Может потому, что я в Cygwin'е запускал? Хотя там в принципе-то чистая математика...
ufm
Dec. 20th, 2010 04:12 pm (UTC)
Не, наверное потому-что я это на эрланге написал. :)
ufm
Dec. 20th, 2010 04:15 pm (UTC)
find_less() ->
find(1)
.

find(L) ->
case rdiv(pow(L,137)) of
true ->
L;
false ->
L rem 100000 =:= 0 andalso io:format("~p ~p~n", [calendar:local_time(),L]),
find(L+1)
end
.

rdiv(Y) ->
(Y rem 1395667104275780136328137029621666356023102373828208614259008333518048661758896451829091736021396841)
=:= 853850955301866163689247242586471298622619472656175640289466689838635348038838411985760314991260370
.

pow(T, K) ->
pow(1, T, K)
.

pow(Res, _, 0) -> Res;
pow(Res, T, K) ->
case K rem 2 of
0 ->
pow(Res, T * T, K div 2);
1 ->
pow(Res * T, T * T, K div 2)
end
.
brohm
Dec. 20th, 2010 03:05 pm (UTC)
что значит "тупым перебором дошла до 500000"??
ты как организовал тупой перебор, от нуля ++ чтоль?
uncle_asa
Dec. 20th, 2010 03:08 pm (UTC)
Угу :) Как-то так:
m = 1395667104275780136328137029621666356023102373828208614259008333518048661758896451829091736021396841
k = 853850955301866163689247242586471298622619472656175640289466689838635348038838411985760314991260370
for (i = 0; 1; i++)
{
rem = i ^ 137 % m
if (rem == k)
{
print i
break
}
}
brohm
Dec. 20th, 2010 04:14 pm (UTC)
а, сорри, неправильно условие прочитал
(капча зло!)
uncle_asa
Dec. 20th, 2010 04:19 pm (UTC)
Ээээ.... У меня где-то включена капча?
( 18 comments — Leave a comment )