И снова о простых числах Софи Жермен

Более простой способ проверки простых чисел Софи Жермен на простоту

Год назад я писал о генерации простых чисел Софи Жермен. Вкратце напомню: p — простое число Софи Жермен, если q = 2p+1, тоже простое число. Простые числа Софи Жермен применяются в криптографии (в частности, в протоколе обмена ключами Диффи–Хеллмана–Меркле). Ранее я использовал вероятностный метод Рабина–Миллера для проверки обоих чисел (p и q) на простоту. Вероятностная проверка (вкупе с другими [...]

← Вернуться к полной версии записи «И снова о простых числах Софи Жермен»…

Автор: Vladimir; опубликовано в: C/C++; метки: C/C++, GMP, простые числа, Софи Жермен

22
Апр
2009

Комментарии к статье «И снова о простых числах Софи Жермен» (4) »

Sphynkx

Ноябрь 22, 2009 в 02:56

Спасибо за простые и наглядные примерчики кода!! Сейчас как раз знакомлюсь с GMP –
разбираюсь что к чему, читаю доки, примеры, тыкаюсь методом тыка… ) Кое в чем помогли Ваши программы.

Кстати, sophie1.c у меня выдавала segfault (gcc ver. 4.1.2). Дело в sj_mpz_pow(). Там у Вас переменные не инициализированы в момент присваивания. Вот так все заработало:

[-]

View Code C

mpz_init_set_ui(y, 1);
mpz_init_set(i, n);
mpz_init_set(z, x);

Ответить
- Vladimir
  
  Ноябрь 22, 2009 в 05:37
  
  Спасибо, код поправил
  
  Только вместо mpz_init_set_ui(y, 1); должно быть mpz_set_ui(y, 1); — передаваемые в процедуру параметры инициализируются вызывающей стороной. Два вызова mpz_init() без mpz_clear() чреваты утечкой памяти.
  
  Ответить
Ваня

Сентябрь 27, 2010 в 23:15

Для устранения утечек памяти я бы советовал Deleaker

Ответить
- Wandering Soul
  
  Сентябрь 28, 2010 в 11:14
  
  Или классика жанра — Valgrind
  
  Ответить