tek4

Số Carmichael và thuật toán tìm số Carmichael

by - September. 21, 2021
Kiến thức
<p>Số n được cho l&agrave; số Carmichael nếu n&oacute; thỏa m&atilde;n điều kiện số học modulo sau:</p> <pre class="language-markup"><code>power(b, n-1) mod n = 1, với mọi b trong khoảng từ 1 tới n sao cho b v&agrave; n l&agrave; nguy&ecirc;n tố c&ugrave;ng nhau, hay, gcd(b, n) = 1</code></pre> <p style="text-align: justify;">Cho một số nguy&ecirc;n dương n, b&agrave;i to&aacute;n x&aacute;c định xem n&oacute; c&oacute; phải l&agrave; một số Carmichael hay kh&ocirc;ng l&agrave; một b&agrave;i to&aacute;n c&oacute; &yacute; nghĩa quan trọng trong Phương ph&aacute;p kiểm tra nguy&ecirc;n tố x&aacute;c suất Fermat.</p> <p>Chẳng hạn:</p> <pre class="language-markup"><code>Đầu v&agrave;o: n = 8 Đầu ra : false Giải th&iacute;ch: 8 kh&ocirc;ng phải l&agrave; số Carmichael do 3 l&agrave; nguy&ecirc;n tố c&ugrave;ng nhau với 8 v&agrave; 3^{8-1} mod 8 = 2187 % 8 kh&aacute;c 1. Đầu v&agrave;o: n = 561 Đầu ra: true</code></pre> <p>&Yacute; tưởng rất đơn giản, ch&uacute;ng ta lặp qua tất cả c&aacute;c số từ 1 đến n v&agrave; với mọi số nguy&ecirc;n tố c&ugrave;ng nhau, ch&uacute;ng ta kiểm tra xem lũy thừa thứ (n-1) của n&oacute; theo modulo n c&oacute; l&agrave; 1 hay kh&ocirc;ng.<br />Dưới đ&acirc;y l&agrave; một chương tr&igrave;nh để kiểm tra xem một số nhất định c&oacute; phải l&agrave; Carmichael hay kh&ocirc;ng.</p> <pre class="language-c"><code>#include &lt;stdio.h&gt; int gcd(int a, int b) { if (a &lt; b) return gcd(b, a); if (a % b == 0) return b; return gcd(b, a % b); } int power(int x, int y, int mod) { if (y == 0) return 1; int temp = power(x, y / 2, mod) % mod; temp = (temp * temp) % mod; if (y % 2 == 1) temp = (temp * x) % mod; return temp; } bool isCarmichaelNumber(int n) { for (int b = 2; b &lt; n; b++) { // Nếu "b" l&agrave; nguy&ecirc;n tố c&ugrave;ng nhau với n if (gcd(b, n) == 1) // V&agrave; pow(b, n-1)%n kh&aacute;c 1, // return false. if (power(b, n - 1, n) != 1) return false; } return true; } int main() { printf(isCarmichaelNumber(500)); printf(isCarmichaelNumber(561)); printf(isCarmichaelNumber(1105)); return 0; }</code></pre> <p>Tr&ecirc;n đ&acirc;y l&agrave; kh&aacute;i niệm v&agrave; giải thuật về gi&aacute; trị số Carmichael, nếu c&aacute;c bạn c&oacute; bất kỳ thắc mắc n&agrave;o hoặc b&igrave;nh luận g&oacute;p &yacute;, c&aacute;c bạn c&oacute; thể gửi c&acirc;u hỏi l&ecirc;n tr&ecirc;n nh&oacute;m cộng của TEK4.VN nh&eacute;!</p> <hr /> <p style="text-align: center;"><em><strong>Fanpage Facebook:</strong>&nbsp;<a href="https://www.facebook.com/tek4.vn/">TEK4.VN</a></em>&nbsp;</p> <p style="text-align: center;"><em><strong>Tham gia cộng đồng để chia sẻ, trao đổi v&agrave; thảo luận:</strong>&nbsp;<a href="https://www.facebook.com/groups/tek4.vn/">TEK4.VN - Học Lập Tr&igrave;nh Miễn Ph&iacute;</a></em></p>