대학 과정에서 MASH-2 해시 함수를 사용했으며 시험에서 과 같은 질문 ((62500)^257)) mod (238194151)을 과학적인 계산기 만. 이제 나는 a^b (mod n) 이론을 알고 있지만 위에 제시된 문제는 수동으로 계산하기가 어렵다. 나는 이것을 해결하는 데 약 15 분이 걸릴 것이라고 생각한다. 나는 이것을 할 더 빠른 방법이 있는지 알고 싶다. 또는 바이너리로 수행 할 수있는 방법이 있더라도 (바이너리로 변환 한 후 일부 조작). 나는 과학적인 계산기로 이것을 손으로 할 수 있어야한다.MASH-2 해시 함수
a = 62500 = 2² ⋅ 5⁶의 소수 요소 분해는 매우 간단합니다.
먼저 (2²)²⁵⁷과 (5⁶)²⁵⁷을 계산하고 제품을 계산할 수 있습니다.
그러나 내가보기에 문제는 n = 238194151에 대한 과학 계산기가 n²을 올바르게 계산할 수 없다는 것입니다. 계산기가이 작업을 수행 할 수 있다면 문제가되지 않습니다.
gcd(a, b) = 1 이후 CRT도 사용할 수 있지만 공학용 계산기 만 사용하면 소수 요소 n = 13 ⋅ 59 ⋅ 310553을 찾을 수 있는지 확실하지 않습니다. 그렇다면 훨씬 쉽게 할 수 있습니다. a²⁵⁷ mod (13⋅59)과 a²⁵⁷ mod 310553을 계산하고 그 결과를 CRT와 함께 입력하면됩니다.
Exponentiation by squaring 만 사용할 수 있으므로 8 개의 정사각형을 계산하면됩니다.
나는이 질문을했는지 기억이 나지 않는다. 어쨌든 당신의 설명이 합리적으로 들리므로 정답을 알려 드리겠습니다. 고맙습니다. –
작성된 것처럼 전혀 문제가되지 않지만 물음표가없고 문장 구조가 직접 물음표가 필요한 문장은 없습니다. 그 질문을 남겨두고,이 질문은 주제에 관한 것입니다. (수학의 강렬한 냄새가납니다.) 학생이 이미 공부 한 내용을 이미 적용했다는 증거를 보여 준다면 연구 지원에 대한 간청이 훨씬 더 좋은 답을 얻습니다. 가르치고 붙 잡혔다. 지금까지 뭐 해봤 어 ? –
나는 모든 것을 시도했다는 것을 믿으십시오. 제 질문은 분명합니다. 오일러 이론보다 더 빠른 방법으로^b (mod n)을 계산할 수있는 방법이 있습니까? –
나는 머리 꼭대기를 기억하지 못한다. 그러나 a와 m이 상대적으로 소수 일 때 문제를 크게 단순화하는 수 이론에 정리가 있다고 믿는다. 오늘 밤 직장에서 집에 돌아갈 때 이것이 여전히 열려 있으면 나는 수적 이론 서적을 찾으려고 노력할 것입니다. – bigbenbt