Я пишу криптографическую библиотеку на Хаскеле, чтобы узнать о криптографии и монадах. ( Не для реального использования!) Тип моей функции для тестирования простоты
prime :: (Integral a, Random a, RandomGen g) => a -> State g Bool
Итак, как вы можете видеть, я использую Государственную Монаду, чтобы у меня не было потока через генератор все время. Внутренне функция простого числа использует критерий Миллера-Рабина, который полагается на случайные числа, поэтому функция простого числа также должна полагаться на случайное число. Это имеет смысл в некотором смысле, так как основная функция выполняет только вероятностный тест.
Только для справки, вся основная функция приведена ниже, но я не думаю, что вам нужно ее читать.
-- | findDS n, for odd n, gives odd d and s >= 0 s.t. n=2^s*d.
findDS :: Integral a => a -> (a, a)
findDS n = findDS' (n-1) 0
where
findDS' q s
| even q = findDS' (q `div` 2) (s+1)
| odd q = (q,s)
-- | millerRabinOnce n d s a does one MR round test on
-- n using a.
millerRabinOnce :: Integral a => a -> a -> a -> a -> Bool
millerRabinOnce n d s a
| even n = False
| otherwise = not (test1 && test2)
where
(d,s) = findDS n
test1 = powerModulo a d n /= 1
test2 = and $ map (\t -> powerModulo a ((2^t)*d) n /= n-1)
[0..s-1]
-- | millerRabin k n does k MR rounds testing n for primality.
millerRabin :: (RandomGen g, Random a, Integral a) =>
a -> a -> State g Bool
millerRabin k n = millerRabin' k
where
(d, s) = findDS n
millerRabin' 0 = return True
millerRabin' k = do
rest <- millerRabin' $ k - 1
test <- randomR_st (1, n - 1)
let this = millerRabinOnce n d s test
return $ this && rest
-- | primeK k n. Probabilistic primality test of n
-- using k Miller-Rabin rounds.
primeK :: (Integral a, Random a, RandomGen g) =>
a -> a -> State g Bool
primeK k n
| n < 2 = return False
| n == 2 || n == 3 = return True
| otherwise = millerRabin (min n k) n
-- | Probabilistic primality test with 64 Miller-Rabin rounds.
prime :: (Integral a, Random a, RandomGen g) =>
a -> State g Bool
prime = primeK 64
Дело в том, что везде, где мне нужно использовать простые числа, я должен также превратить эту функцию в монадическую функцию. Даже там, где, казалось бы, нет никакой случайности. Например, ниже моя прежняя функция для восстановления секрета в Схеме обмена секретами Шамира. Детерминированная операция, верно?
recover :: Integral a => [a] -> [a] -> a -> a
recover pi_s si_s q = sum prods `mod` q
where
bi_s = map (beta pi_s q) pi_s
prods = zipWith (*) bi_s si_s
Хорошо, это было, когда я использовал наивную, детерминистическую функцию теста на простоту. Я еще не переписал функцию recover, но я уже знаю, что функция beta опирается на простые числа, и, следовательно, она и recover тоже будут. И обеим придется перейти от простых не-монадических функций к двум монадическим функциям, хотя причина, по которой они используют Государственную монаду / случайность, очень глубока.
Не могу не думать, что теперь весь код становится более сложным, потому что он должен быть монадическим. Я что-то упускаю или это всегда так в таких ситуациях в Haskell?
Одно решение, о котором я мог подумать, это
prime' n = runState (prime n) (mkStdGen 123)
и используйте prime' вместо этого. Это решение поднимает два вопроса.
- Это плохая идея? Я не думаю, что это очень элегантно.
- Где должен быть этот "переход" от монадического к немонадному коду? Потому что у меня также есть такие функции
genPrime:
_
genPrime :: (RandomGen g, Random a, Integral a) => a -> State g a
genPrime b = do
n <- randomR_st (2^(b-1),2^b-1)
ps <- filterM prime [n..]
return $ head ps
Возникает вопрос: делать ли «обрез» до или после genPrime и т. П.