0.00 ₫(0 items)

    Thách đố về giả thuyết số nguyên tố sinh đôi

    Số nguyên tố sinh đôi là một cặp số nguyên tố́ liền nhau có dạng (n, n+2), bắt đầu từ (3,5), sau đó là (5,7), (11,13), v.v. Số nguyên tố sinh đôi cực hiếm, nhưng cứ sau vài năm người ta lại tìm thấy một cặp số sinh đôi lớn hơn. Từ thời Hy Lạp cổ đại Ơclit (Euclide) đã tin rằng có vô số các số nguyên tố sinh đôi. Tuy nhiên, sau nhiều thế kỷ vẫn chưa có ai chứng minh được điều này, và cho tới nay người ta vẫn coi đây là một điều bí hiểm.

    Ngày nay người ta gọi điều này là giả thuyết số nguyên tố sinh đôi. Cái khó ở đây là không có công thức mô tả số nguyên tố. Để tìm các số nguyên tố trong một bảng số thì người ta thường loại bỏ dần các hợp số của các số nguyên tố trước đó. Phương pháp này được gọi là sàng Ơ-ra-tô-xten (Erathostenes) theo tên một nhà toán học Hy Lạp cổ đại. Tuy nhiên phương pháp này chỉ hiệu quả khi tìm các số nguyên tố nhỏ hơn hàng chục triệu.



    Năm 1849, nhà toán học Pháp de Polignac đưa ra giả thuyết tổng quát hơn là với mọi số chẵn k ≥ 2 tồn tại vô hạn các cặp số nguyên tố m, n sao cho m – n = k. Nhưng giả thuyết này cũng chưa được giải quyết cho bất kỳ một số k nào. Thậm chí một giả thuyết yếu hơn là tồn tại vô hạn cặp số nguyên tố m, n sao cho m – n ≤ ki, cũng bị nhiều nhà khoa học cho rằng chưa thể giải quyết bằng các phương pháp nghiên cứu hiện có. Nhà số học Goldston cho rằng “đây là một trong những vấn đề mà ta không chắc loài người có thể giải được”.

    Nhưng vào ngày 17/4/2013, tòa soạn tạp chí Annals of Mathematics nhận được bản thảo của một nhà toán học vô danh là Yitang Zhang khẳng định đã giải quyết được giả thuyết yếu trên cho k = 70 triệu. Tuy k = 70 triệu còn xa với mục tiêu k = 2, nhưng đây có thể coi là bước đi đột phá về giả thuyết số nguyên tố sinh đôi. Khoảng cách giữa 2 và 70 triệu tuy lớn nhưng vẫn không thấm thoát gì so với khoảng cách giữa 70 triệu và vô hạn!




    Nhà toán học vô danh “lấy nghề làm niềm vui”




    src=

    Yitang Zhang


    Yitang Zhang sinh năm 1955 tại Trung Quốc. Năm 1985, ông sang Mỹ làm nghiên cứu sinh sau khi tham dự lớp cao học được tổ chức bởi nhà toán học nổi tiếng Shiing-Shen Chern ở Bắc Kinh. Ông bảo vệ luận án tiến sĩ năm 1991 sau 7 năm làm nghiên cứu sinh tại Đại học Purdue dưới sự hướng dẫn của Tzuong-Tsieng Moh. Đề tài luận án do ông chọn là về giả thuyết Jacobi. Đây là một giả thuyết lâu đời được nhà toán học Stefen Smale (giải thưởng Fields năm 1966) coi là một trong 18 bài toán của thế kỷ 21. Zhang tưởng rằng mình đã chứng minh được giả thuyết này, nhưng sau đó người ta phát hiện ra một kết quả của Moh được Zhang dùng trong chứng minh của mình có vấn đề.  Cho đến nay, Zhang mới công bố hai công trình toán học vào các năm 1985 (năm bảo vệ luận án thạc sĩ) và 2001. Ông là dạng nhà toán học chỉ chuyên tâm giải quyết các vấn đề khó. Cuộc đời của Zhang có nhiều gian truân. Sau khi bảo vệ luận án tiến sĩ, ông không xin được việc làm ở các trường đại học và đã phải làm nhiều việc thời vụ như dọn bàn, đưa đồ ăn,  trực khách sạn, kế toán, v.v. Mãi đến năm 1999, ông mới được nhận vào làm giảng viên ở Đại học New Hampshire nhưng không có chức danh chính thức và làm việc ở đó cho đến ngày nay. Andrew Granville, một nhà số học có tiếng, nhận xét về Zhang: “Không ai biết anh ta là ai. Vậy mà bỗng nhiên anh ta chứng minh được một trong những kết quả lớn nhất trong lịch sử lý thuyết số.”

    Tự nhận mình là một người rụt rè, nhưng Zhang nói: “khi làm báo cáo và tập trung vào toán học, tôi quên mất sự  rụt rè của tôi”. Có người hỏi ông có cảm thấy cay đắng về số phận long đong của mình không thì ông trả lời “Cái đầu của tôi luôn bình thản. Tôi không quan tâm nhiều lắm đến tiền tài hay  danh vọng. Tôi thích giữ im lặng và tiếp tục làm những gì mà tôi quan tâm”. Lại có người hỏi liệu ông có khuyên người khác làm theo ông không thì ông trả lời “khó nói lắm” và “tôi chọn đường đi của mình và đó là con đường của riêng tôi”.

    Ngay sau khi công bố kết quả mới liên quan đến giả thuyết yếu về số nguyên tố sinh đôi, Zhang nhận được nhiều giải thưởng danh giá và được nhiều trường đại học danh tiếng mời đến làm việc. Tuy nhiên ông vẫn quyết định ở lại Đại học New Hampshire. Tại Đại hội Toán học thế giới năm nay ở Seoul, ông được mời làm báo cáo toàn thể đặc biệt ngang hàng với các báo cáo giải thưởng Fields.

    Gần đây ông bắt đầu nghiên cứu một đề tài khác và không muốn thổ lộ cho người khác biết. Ông chỉ nói, “Hy vọng nó sẽ cho một kết quả tốt”. Theo Tzuong-Tsieng Moh, thầy của Zhang, thì ông thích câu nói của Khổng Tử rằng “người biết nghề không sánh được với người yêu nghề, người yêu nghề không sánh được với người lấy nghề làm niềm vui”.

    Cái sàng của Zhang

    Công trình của Zhang đã được thẩm định và được công bố vào tháng 3 năm 2014, có xuất xứ từ một bài báo của Goldston, Pintz và Yildirim (GPY) công bố năm 2005. Bài báo này chứng minh rằng luôn tồn tại các cặp nguyên tố liền nhau mà khoảng cách giữa chúng nhỏ hơn rất nhiều so với độ lớn của chúng. Để có được kết quả này GPY đã đưa ra một phương pháp để lọc các cặp nguyên tố liền nhau giống như cái sàng Ơ-ra-tô-xten.  Ngoài ra, họ còn dùng một tham số gọi là mức phân bố số nguyên tố. Người ta biết rằng tham số này lớn hơn hoặc bằng ½ và điều này đủ để chứng minh kết quả của GPY. Họ cũng nhận xét rằng nếu tham số này lớn hơn ½ thì dùng cái sàng của họ sẽ chứng minh được tồn tại vô hạn cặp số nguyên tố liền nhau bị chặn bởi một số k nào đó. Trong bài báo của mình, GPY viết rằng kết quả của họ “chỉ cách bề dày một sợi tóc đến kết quả đó”.

    Zhang từng nghiên cứu lý thuyết số trong luận án cao học nên ông để ý đến bài báo của GPI. “Câu văn này lập tức gây ấn tượng với tôi”, ông hồi tưởng lại. Sau đó ông bắt đầu tìm cách mở rộng kết quả của GPY. Trong ba năm sau đó, ông không tiến thêm được một bước nào. “Tôi quá mỏi mệt”, ông nói. Hè năm 2012, ông quyết định nghỉ một chút và đi thăm một người bạn ở Colorado mà không mang bất kỳ tài liệu toán học nào theo mình. Tuy nhiên ông vẫn bị ám ảnh bởi giả thuyết chặn trên cho khoảng cách các số nguyên tố. Trong một lúc mơ màng ngoài vườn của bạn, ông chợt tìm ra ý tưởng cho lời giải. “Tôi lập tức tin nó đúng”. Để giải quyết giả thuyết ông thấy không cần thiết phải lọc tất cả các số mà chỉ cần lọc các số có thừa số nguyên tố không lớn lắm. Như vậy là cái sàng của ông tuy không tốt bằng cái sàng của GPI nhưng lại có độ linh hoạt đủ để giải quyết vấn đề. Theo ông, “có rất nhiều cơ may trong sự nghiệp của bạn nhưng quan trọng là bạn phải luôn luôn suy nghĩ”.

    Kết quả của Zhang lập tức dẫn đến câu hỏi tại sao tồn tại vô số cặp số nguyên tố liền nhau có khoảng cách nhỏ hơn 70 triệu mà không bị chặn bởi một số nhỏ hơn. Thực ra, Zhang dùng chặn 70 triệu chỉ để làm cho chứng minh đơn giản hơn. Đến cuối tháng 5/2013, các nhà toán học đã cải thiện chặn trên của Zhang xuống còn 60 triệu. Tháng 6/2013 nhà toán học Terence Tao (giải thưởng Fields năm 2006) lập một đề án trực tuyến Polymath để mọi người có thể hợp tác nghiên cứu qua mạng để tìm các chặn trên nhỏ hơn nữa. Trong vài tuần sau đó, tình hình cải thiện theo một tốc độ chóng mặt, “cứ khoảng nửa tiếng lại có một chặn trên tốt hơn”, Tao hồi tưởng lại. Đến cuối tháng 7/2013, người ta đã đưa con số 70 triệu trong chứng minh của Zhang xuống còn 4680. Đề án Polymath này hiện đang được tập trung vào việc viết một bài báo tập thể về kết quả này. Bản thảo hiện nay đã dài hơn 150 trang, dự kiến sẽ công bố trong tạp chí “Algebra and Number Theory”.

    Phương pháp của Maynard và cuộc chạy đua trực tuyến

    /><br /> <br /> </span><span><span><em><span><span>James Maynard hiện đang làm hậu tiến sỹ tại Đại học Montreal.</span></span></em></span></span></td> <p> <br /> </tr> <p> <br /> </tbody> <p> <br /> </table> <p> <br /> Câu chuyện vẫn chưa dừng lại ở đây vì đến ngày 19/11/2013, có một nhà toán học trẻ tên là James Maynard đưa ra chặn trên mới là 600 trên ArXiv với một chứng minh hoàn toàn độc lập với chứng minh của Zhang. Đặc biệt hơn, phương pháp của Maynard còn cho phép nghiên cứu không chỉ các cặp số nguyên tố mà còn cả các bộ số nguyên tố liền nhau. Maynard vừa mới bảo vệ luận án tiến sĩ về sàng số nguyên tố và hiện đang làm việc sau tiến sĩ tại Đại học Montreal. </span></p> <p><span>Công trình của Maynard, theo một nghĩa nào đó, cũng khởi thủy từ bài báo của GPY. Trước đó, hai tác giả Goldston va Yildirim đã từng công bố một phương pháp lọc các cặp số nguyên tố liền nhau. Ngay sau đấy người ta phát hiện ra phương pháp này có lỗi. Sau khi GPY thay đổi phương pháp lọc để tránh lỗi trên thì mọi người đổ xô vào nghiên cứu bài báo mới mà quên hẳn mất phương pháp lọc cũ. Cách đây hơn một năm, Maynard quyết định xem lại bài báo của Goldston và Yildirim. Anh phát hiện thấy có thể sửa lỗi để có một phương pháp lọc hiệu quả hơn là cách GPY đã làm. Ý tưởng của Maynard rất đơn giản. Người hướng dẫn sau tiến sĩ của Maynard là Granville nhận xét rằng “Đó là một điều mà những người như tôi sẽ gõ vào trán và tự nhủ ta có thể chứng minh cái này bảy năm trước đây”. </span></p> <p><span>Ngay sau công bố của Maynard, một đề án trực tuyến Polymath khác được lập ra nhằm sử dụng phương pháp của Maynard để đưa ra các chặn trên nhỏ hơn nữa. Khi bài báo này được viết, người ta đã giảm chặn trên xuống còn 252. Các đề án Polymath thu hút được rất nhiều chuyên gia từ các hướng nghiên cứu khác nhau tham gia. Họ có thể giải quyết các bước khác nhau trong kỹ thuật chứng minh của Zhang và Maynar để tìm các chặn trên nhỏ hơn. Công việc của họ hoàn toàn phụ thuộc lẫn nhau. Nếu một người tìm ra kết quả hay ý tưởng mới thì người khác cũng phải thay đổi tương ứng các dữ kiện nghiên cứu của mình. Chuyên gia tính toán Andrew Sutherland của Viện công nghệ Massachusetts nói rằng “Luật chơi thay đổi hằng ngày”, “trong lúc tôi đang ngủ thì các đồng nghiệp ở châu Âu đã tìm thấy một chặn trên mới. Nhiều khi, tôi thức đến 2 giờ sáng để thông báo một ý tưởng mới”. </span></p> <p><span>Trong khi Zhang và Maynard là dạng những nhà toán học tài năng nghiên cứu một mình vài năm cho đến khi đạt được một kết quả làm chấn động mọi người thì các đề án Polymath khác hẳn. Chúng cần một sự hợp tác toàn diện từ nhiều người nhằm giải quyết những vấn đề toán học phức tạp và thường có kết quả rất nhanh. Tuy nhiên, không phải vấn đề toán học nào cũng phù hợp với cách nghiên cứu tập thể. Theo Tao thì “cần có những người sẵn sàng làm việc đơn độc và vượt qua những cách suy nghĩ thông thường”. </span></p> <p><strong><em><span>Thách đố vẫn tiếp tục</span></em></strong></p> <p><span> </p> <table width=

    /><br /> <br /> </span><span><span><span><em>Không phải vấn đề toán học nào cũng phù hợp với cách nghiên cứu tập thể, mà cần có những người sẵn sàng làm việc đơn độc và vượt qua những cách suy nghĩ thông thường.</em><br /> <br /> <strong><em>Terence Tao</em></strong></span></span></span></td> <p> <br /> </tr> <p> <br /> </tbody> <p> <br /> </table> <p> <br /> Chúng ta có thể hy vọng gì từ các kỹ thuật chứng minh của Zhang và Maynard cho việc giải quyết giả thuyết số nguyên tố sinh đôi? Phương pháp của Zhang chỉ có thể dẫn đến chặn trên 16 nếu giải quyết được hết các vướng mắc còn tồn tại. Còn phương pháp của Maynard cũng chỉ có thể giảm chặn trên xuống đến 12 là cùng. Tao cho biết nếu dùng thêm một giả thuyết của Elliot-Halberstam thì có thể đưa chặn trên xuống còn 6. Theo Maynard thì khó có thể cải tiến các phương pháp quen biết để nhận được chặn trên cuối cùng là 2. Anh nhận xét “Tôi cảm thấy chúng ta cần phải có đột phá về cách tiếp cận thì mới giải được giả thuyết số nguyên tố sinh đôi”. Như vậy là chưa có gì đảm bảo trong một tương lai gần người ta sẽ giải quyết được giả thuyết này. Đây vẫn tiếp tục là một thách thức đối với trí tuệ  con người. </span><br /> <br /> <em><br /> <br /> </em><strong><span>Tài liệu tham khảo</span></strong></p> <p><span>Kenneth Chang, Solving a Riddle of Primes, http://www.nytimes.com/2013/05/21/ science/solving-a-riddle-of-primes.html?_r=0</span></p> <p><span>Erica Klareich, Sudden Progress on Prime Number Problem Has Mathematicians Buzzing, http://www.wired.com/wiredscience/2013/11/prime/all/</span></p> <p><span>Erica Klareich, Unheralded Mathematician Bridges the Prime Gap, https://www.simonsfoundation.org/quanta/20130519-unheralded-mathematician-bridges-the-prime-gap/</span></p> <p><span>Leslie Katz, Yitang Zhang: A prime-number proof and a world of persistence, http://news.cnet.com/8301-17938_105-57618696-1/yitang-zhang-a-prime-number-proof-and-a-world-of-persistence/</span></p> <p><span>Maggie McKee, First proof that infinitely many prime numbers come in pairs, http://www.nature.com/news/first-proof-that-infinitely-many-prime-numbers-come-in-pairs-1.12989</span></p> <p><span>Tzuong-Tsieng Moh, “Zhang, Yitang’s life at Purdue, http://www.math.purdue.edu /~ttm/ZhangYt.pdf</span></p> <p><span>i Giả thuyết yếu này được gọi là chặn trên cho khoảng cách các số nguyên tố, tuy nó không tương đương với giả thuyết của de Polignac, nhưng trong trường hợp k = 2 thì nó chính là giả thuyết số nguyên tố sinh đôi</span></p> </div> <h4><span class=Vì sao 1 không phải là số nguyên tố? | Trường THPT Ngô Gia Tự

    Vì sao 1 không phải là số nguyên tố?

    width=

    Toàn bộ số tự nhiên được chia làm ba loại: Loại 1 là các số nguyên tố (như 2,3,5,7,11,13,…), Loại 2 là các hợp số (4,6,8,9,10,…) . Số “1” không phải là số nguyên tố, cũng không phải là hợp số nên nó là một loại riêng thứ 3. Số nguyên tố là những số chỉ chia hết cho 1 và chính nó, còn hợp số có thể chia hết cho những số khác. Ví dụ, hợp số 6, ngoài chia hết cho 1 và 6 ra, nó còn chia hết cho 2 và 3. Đây là lý do chính để chia ra thành loại hợp số và số nguyên tố. Nhưng số 1 cũng chia hết cho 1 và chính nó, vì sao không gọi là số nguyên tố ? Nếu 1 là số nguyên tố thì chỉ cần chia số tự nhiên thành 2 loại có tốt hơn không ? Để trả lời vấn đề này, trước tiên ta phải đặt vấn đề vì sao phải bàn đến số nguyên tố. Ví dụ số 3003 có thể chia hết cho số nguyên tố nào? Cũng có nghĩa là số nào là thừa số của 3003 ? Đương nhiên ta có thể xét tất cả các số từ 1 đến 3003, nhưng như vậy thì rất tốn công.

    Chúng ta biết rằng, hợp số có thể là tích của nhiều số nguyên tố, tức là nhân nhiều số nguyên tố với nhau, nói cách khác, chính là phân tích thành thừa số nguyên tố.Đương nhiên, mỗi hợp số đều có thể phân tích thành thừa số nguyên tố và chỉ có một kết quả mà thôi (tất nhiên không kể đến thứ tự các thừa số).
    Ví dụ : số 3003 có thể phân tích thành 3.7.11.13

    Bây giờ ta quay trở lại vấn đề vì sao 1 không phải là số nguyên tố. Nếu 1 được coi là số nguyên tố thì khi phân tích một hợp số thành thừa số nguyên tố, đáp án sẽ không phải là duy nhất nữa!

    Ví dụ : Phân tích số 3003 thành thừa số nguyên tố sẽ xảy ra các trường hợp sau:

    3003 = 3.7.11.13
    3003 = 1.3.7.11.13
    3003 = 1.1.3.7.11.13

    …………

    Như vậy, khi phân tích có thể tuỳ ý thêm các thừa số 1 vào như vậy quả thực là không cần thiết chút nào, và kết quả phân tích lại không duy nhất, chỉ tăng thêm những phiền phức không cần thiết. Vì vậy 1 không được coi là số nguyên tố.

    ps: Khái niệm số nguyên tố là rất cơ bản nhưng nhiều người từ giáo viên đến học sinh vẫn hay nhầm: “số nguyên tố là số tự nhiên chỉ chia hết cho 1 và chính nó” mà quên rằng: “số nguyên tố phải lớn hơn 1”.

    Nguồn: http://diendantoanhoc.net/

    Số nguyên tố. Hợp số. Bảng số nguyên tố

    Trả lời câu hỏi Bài 14 trang 46 Toán 6 Tập 1
    Trả lời câu hỏi Bài 14 trang 46 Toán 6 Tập 1

    Trả lời câu hỏi Bài 14 trang 46 Toán 6 Tập 1 . Trong các số 7, 8, 9, số nào là số nguyên tố, số nào là hợp số ? Vì sao ?

    Thuật toán Miller – Kiểm tra số nguyên tố

    Thuật toán Miller – Kiểm tra số nguyên tố

    Miller là một biến thể của thuật toán Rabin-Miller,
    dùng để kiểm tra xem một số nguyên có phải là số nguyên tố hay không.

    Bài này có dùng các kiển thức về đồng dư, nếu bạn chưa biết thì nên đọc bài toán đồng dư.

    Xét số lẻ , để kiểm tra xem có phải là số nguyên tố hay không, ta làm như
    sau:

    • Phân tích thành dạng ( và là số nguyên dương, lẻ)
    • Xét mỗi số nguyên trong khoảng
      • Nếu và với mọi từ đến
        thì không phải là số nguyên tố.
    • Nếu vượt qua được tất cả các lần thử với ở trên thì là số nguyên tố.

    Một cách tổng quát thì thuật toán này chưa được chứng minh là đúng. Tính đúng đắn của nó phụ thuộc vào
    giả thuyết Reimann.

    Tuy nhiên, với nhỏ () thì thuật toán đã được kiểm tra và chứng minh là đúng.
    Ngoài ra, ta cũng không cần kiểm tra hết tất các các số nguyên như ở trên, mà chỉ cần dùng một vài số là đủ.

    Bảng sau được sử dụng để kiểm tra số nguyên tố trong thực tế:

    Giới hạn của Các số cần dùng
    2
    2, 3
    31, 73
    2, 7, 61
    2, 13, 23, 1662803
    2, 3, 5, 7, 11
    2, 3, 5, 7, 11, 13
    2, 3, 5, 7, 11, 13, 17
    2, 3, 5, 7, 11, 13, 17, 19, 23
    2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37
    2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41

    Xem bảng trên, ta thấy chỉ cần dùng 3 số thử: 2, 7, 61 là đủ để kiểm tra tính nguyên tố
    của mọi số nguyên 32-bit.

    Để hiểu rõ hơn cách dùng, bạn đọc xem thêm phần dưới.

    Trong phần này mình sẽ dùng Miller để giải 2 bài PNUMBER
    và PRIME1.

    Thuật toán gồm các giai đoạn chính:

    • Phân tích thành dạng .
    • Thử lần lượt các số trong bảng ở trên.
      • Khi thử, ta cần dùng hàm lũy thừa nhanh để tính .

    Ta sẽ lần lượt cài đặt các hàm cơ bản trên. Trước hết, ta khai báo các thư viện và kiểu dữ liệu cần
    sử dụng:

    #include <tuple>
#include <iostream>
using namespace std;
typedef unsigned long long ll;

    Hàm phân tích thành dạng :

    pair<ll, ll> factor(ll n) {
    ll s = 0;
    while ((n & 1) == 0) {
        s++;
        n >>= 1;
    }
    return {s, n};
}

    Hàm tính :

    ll pow(ll a, ll d, ll n) {
    ll result = 1;
    a = a % n;
    while (d > 0) {
        if (d & 1) result = result * a % n;
        d >>= 1;
        a = a * a % n;
    }
    return result;
}

    Hàm kiểm tra xem “nếu và với mọi từ đến
    thì không phải là số nguyên tố”:

    // Trả về false nếu n không phải là số nguyên tố.
bool test_a(ll s, ll d, ll n, ll a) {
    if (n == a) return true;
    ll p = pow(a, d, n);
    if (p == 1) return true;
    for (; s > 0; s--) {
        if (p == n-1) return true;
        p = p * p % n;
    }
    return false;
}

    Hàm cuối cùng: Thử kiểm tra với các khác nhau. Vì ta đang giải bài PNUMBER,
    giới hạn số trong bài này là , tra bảng trên ta thấy chỉ cần kiểm tra với và là đủ:

    // Trả về true nếu n là số nguyên tố,
// false nếu n là hợp số.
bool miller(ll n) {
    if (n < 2) return false;
    if ((n & 1) == 0) return n == 2;
    ll s, d;
    tie(s, d) = factor(n-1);
    return test_a(s, d, n, 2) && test_a(s, d, n, 3);
}

    Xem full code giải bài PNUMBER bằng thuật toán Miller: /code/139

    Bài tương tự với PNUMBER nhưng có giới hạn cao hơn: PRIME1.

    Giới hạn của bài PRIME1 là , nên ta cần dùng , và . Xem code: /code/138.

    Bảng ở trên có thể kiểm tra đến các số lớn hơn 64-bit, tuy nhiên khi cài đặt,
    nếu không sử dụng kiểu số nguyên lớn thì ta chỉ có thể sử dụng thuật toán với
    các số 32-bit.

    Lý do là thuật toán có dùng phép nhân. Khi nhân 2 số 32-bit kết quả phải được
    chứa trong số 64-bit, nhân 2 số 64-bit thì kết quả phải được chứa trong số 128-bit.
    Vì vậy, để không bị tràn số thì thuật toán chỉ có thể dùng với số 32-bit.

    Để khắc phục điều này, ta có thể tự viết hàm để vừa thực hiện nhân vừa thực hiện mod.

    Đây là code tính của Dana Jacobsen trong một
    câu trả lời
    trên Quora:

    #include <stdint.h>

uint64_t mulmod(uint64_t a, uint64_t b, uint64_t n) {
    // if (a >= n) a %= n;   /* Careful attention from the caller */
    // if (b >= n) b %= n;   /* should make these unnecessary.    */
    uint64_t r = 0;
    if ((a|b) < (1ULL << 32)) return (a*b) % n;
    if (a < b) { uint64_t t = a; a = b; b = t; }
    if (n <= (1ULL << 63)) {
        while (b > 0) {
            if (b & 1)  { r += a;  if (r >= n) r -= n; }
            b >>= 1;
            if (b)      { a += a;  if (a >= n) a -= n; }
        }
    } else {
        while (b > 0) {
            if (b & 1)  r = ((n-r) > a) ? r+a : r+a-n;    /* r = (r + a) % n */
            b >>= 1;
            if (b)      a = ((n-a) > a) ? a+a : a+a-n;    /* a = (a + a) % n */
        }
    }
    return r;
}

    Đoạn code trên hơi phức tạp, bạn đọc có thể đọc đoạn code sau để hiểu tư tưởng thuật toán:

    uint64_t mulmod(uint64_t a, uint64_t b, uint64_t n) {
    uint64_t r = 0;
    while (b > 0) {
        if (b % 2 != 0) r = (r + a) % n;
        a = a * 2 % n;
        b = b / 2;
    }
    return r;
}

    Đoạn code ở dưới đơn giản hơn, tuy nhiên nó chạy chậm hơn và chỉ chạy đúng
    vớn n có tối đa 63 bit.

    Thay thế các phép nhân trong code Miller ở phần trên bằng hàm mulmod, ta có thể sử dụng
    được Miller cho các số 64-bit.

    Độ phức tạp của hàm mulmod là .

    Mỗi lần kiểm tra tốn phép nhân, kết hợp với phép ĐPT của phép nhân nữa
    là .

    Vậy độ phức tạp của Miller là với là số các số cần kiểm tra.

    Phân tích thừa số nguyên tố trên CASIO fx-580VN X




    TailieuCasio


    13/07/2018
    Bài Giảng Video


    1,350 Lượt Xem


    Số 1018057 là số nguyên tố lớn nhất mà máy tính CASIO fx-580VN X có thể phân tích được

    Chức năng: Phân tích một số tự nhiên bất kỳ thành thừa số nguyên tố.

    • Máy tính có thể phân tích một số có 10 chữ số.
    • 1018081 là số nguyên tố lớn nhất được kiểm tra.

    Ví dụ: Phân tích số 1018057 thành thừa số nguyên tố.

    Thao tác: 1018057=qx

    width=

    Ví dụ: Phân tích số 2×1018057 thành thừa số nguyên tố.

    Thao tác: 2O1018057=qx

    width=

    width=