2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Реализация алгоритма Миллера Рабина в математике
Сообщение27.03.2011, 01:57 
У меня возникла такая проблема в программе Mathematica. В этой программе есть функция PrimeQ[], которая, собственно и проверяет числа на простоту. Но я хочу написать собственную программу,такого же типа.
Первым этапом я нашёл в википедии псевдокод программы.
Довольно просто можно получить значения S и T. Вот начало программы

Код:
m = 2^200 + 3;
s = 1; While[True, If[Mod[m - 1, 2^s] > 0, Break[]]; s++];
t = (m - 1)/(2^(s - 1));

Но вот дальше возникают проблемы. Программа не хочет возводить случайное число A в степень T. Пишет, что число имеет слишком много десятичных знаков, даже если использовать не случайное число, а очень маленькое AE[2,23]
Но ведь как-то решена эта проблема при создании функции PrimeQ[]
Если у кого-то есть идеи в написании программы, с удовольствие прочитаю

 
 
 
 Re: Реализация алгоритма Миллера Рабина в математике
Сообщение21.04.2011, 22:19 
В алгоритме случайно не возведение в степень по модулю требуется (вижу Mod)? Тогда используйте PowerMod.

 
 
 [ Сообщений: 2 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group