การค้นหาจำนวนตัวหารของจำนวนเต็มใหญ่โดยใช้การแยกตัวประกอบเฉพาะ/กำลังสอง (C#)

ฉันกำลังพยายามหาจำนวนตัวหารของจำนวนเต็ม 64 บิต (มากกว่า 32 บิต)

วิธีแรกของฉัน (สำหรับจำนวนน้อย) คือหารตัวเลขจนได้ผลลัพธ์เป็น 1 นับจำนวนเฉพาะที่ตรงกันแล้วใช้สูตร (1 + P1)(1+ P2)..* (1 + Pn) = จำนวนตัวหาร

ตัวอย่างเช่น:

24 = 2 * 2 * 2 * 3 = 2^3 * 3^1

==> (3 + 1)*(1 + 1) = 4 * 2 = 8 ตัวหาร

        public static long[] GetPrimeFactor(long number)
        {
            bool Found = false;
            long i = 2;
            List<long> Primes = new List<long>();
            while (number > 1)
            {
                if (number % i == 0)
                {
                    number /= i;
                    Primes.Add(i);
                    i = 1;
                }
                i++;
            }
            return Primes.ToArray();
        }

แต่สำหรับจำนวนเต็มมาก วิธีนี้จะต้องใช้การวนซ้ำหลายครั้ง ฉันพบวิธีการที่เรียกว่า Quadratic sieve เพื่อทำการแยกตัวประกอบโดยใช้ ตัวเลขกำลังสอง ตอนนี้การใช้สคริปต์ของฉันอาจง่ายกว่ามากเพราะตัวเลขมีขนาดเล็กกว่ามาก

คำถามของฉันคือ ฉันจะใช้ Quadratic Sieve นี้ได้อย่างไร


quadratic factorization primes sieve
person Bartemis    schedule 22.03.2015    source แหล่งที่มา
comment
คุณต้องเขียนโปรแกรมขนาดใหญ่ และคำถามของคุณก็กว้างเกินไป   -  person President James K. Polk    schedule 22.03.2015
comment
คำถามของฉันคือรหัสเทียมสำหรับตะแกรงกำลังสองนั่นไม่ใช่โปรแกรมใหญ่ใช่ไหม   -  person Bartemis    schedule 22.03.2015

คำตอบ (1)


arrow_upward
2
arrow_downward

ตะแกรงกำลังสองเป็นวิธีการหาตัวประกอบจำนวนมากที่มีจำนวนมาก คิด 10^75 ไม่ใช่ 2^64 ตะแกรงกำลังสองมีความซับซ้อนแม้จะอยู่ในรูปแบบรหัสเทียมที่เรียบง่าย และซับซ้อนกว่านั้นมากหากคุณต้องการให้มันมีประสิทธิภาพ มันเกินความจำเป็นอย่างมากสำหรับจำนวนเต็ม 64 บิต และจะช้ากว่าวิธีอื่นๆ ที่เชี่ยวชาญเฉพาะสำหรับจำนวนที่น้อยเช่นนี้

ถ้าการแบ่งการทดลองช้าเกินไปสำหรับคุณ ขั้นตอนต่อไปที่มีความซับซ้อนคือวิธี rho ของ John Pollard สำหรับจำนวนเต็ม 64 บิต คุณอาจต้องการทดลองใช้หารด้วยขีดจำกัดเล็กๆ อาจเป็นจำนวนเฉพาะที่น้อยกว่าพัน แล้วเปลี่ยนเป็น rho ต่อไปนี้เป็นรหัสหลอกง่ายๆ เพื่อค้นหาปัจจัยเดียวของ n; เรียกมันซ้ำๆ บนโคแฟคเตอร์แบบผสมเพื่อทำให้การแยกตัวประกอบสมบูรณ์:

function factor(n, c=1)
    if n % 2 == 0 return 2
    h := 1; t := 1
    repeat
        h := (h*h+c) % n
        h := (h*h+c) % n
        t := (t*t+c) % n
        g := gcd(t-h, n)
    while g == 1
    if g is prime return g
    return factor(g, c+1)

มีวิธีอื่นในการแยกตัวประกอบจำนวนเต็ม 64 บิต แต่วิธีนี้จะช่วยให้คุณเริ่มต้นได้ และอาจเพียงพอสำหรับวัตถุประสงค์ส่วนใหญ่ คุณอาจค้นหาอัลกอริธึม rho แบบต่างๆ ของ Richard Brent เพื่อการเร่งความเร็วเล็กน้อย หากคุณต้องการทราบข้อมูลเพิ่มเติม ฉันขอแนะนำบทความ การเขียนโปรแกรมด้วย Prime Numbers อย่างสุภาพ ที่บล็อกของฉัน

person user448810    schedule 23.03.2015