标签: factorization

我正在努力学习F#所以我访问了Project Euler,目前正在研究问题3.

13195的主要因素是5,7,13和29.

600851475143的最大主要因素是什么？

有些事情需要考虑:

1. 我的首要任务是学习良好的功能习惯.
2. 我的第二个优先事项是我希望它快速有效.

在以下代码中,我标记了此问题涉及的部分.

let isPrime(n:int64) = 
    let rec check(i:int64) = 
        i > n / 2L or (n % i <> 0L && check(i + 1L))
    check(2L) 

let greatestPrimeFactor(n:int64) =
    let nextPrime(prime:int64):int64 = 
        seq { for i = prime + 1L to System.Int64.MaxValue do if isPrime(i) then yield i }  
        |> Seq.skipWhile(fun v -> n % v <> 0L) 
        |> Seq.hd
    let rec findNextPrimeFactor(number:int64, prime:int64):int64 =
        if number = 1L then prime …

因为在我的头脑中分解二次方程只是发生了,并且自从我学会了之后就已经这样做了 - 我将如何开始在Python中编写二次方因子？

我们正在检查RSA算法,并想知道将intel i-7内核(@ 2.50 gHz)分解RSA公钥需要多长时间.

我们为此写了一段java,我不知道它有多有效

public static String factorise(long l)
{
    double a = Math.floor(Math.sqrt(l));
    while(l/a != Math.round(l/a))
    {
        a--;
    }
    return (long)a + ", " + (long)(l/a);    
}

使用大约2 ^ 45的数字,它花了大约33毫秒.从理论上讲,需要多长时间才能将数字分解为2 ^ 1024左右？

提前致谢 :)

我正在尝试在Python中实现Pollard的P-1因式分解。请注意，Rho方法有一些答案，但是此p-1是不同的，关于Wiki-1，我可以在这里给您提供的最好的是Wiki和Wolfram：

http://en.wikipedia.org/wiki/Pollard的s_p_％E2％88％92_1_algorithm

http://mathworld.wolfram.com/Pollardp-1FactorizationMethod.html

这是n中的一个因数，但始终找不到p。np和sp分别来自numpy和scipy。因此sp.uint64的内置函数是一个无符号的long 64 int（由于期望的整数的大小），np.prod（p）是列表p的累积乘积pi：

def pm1_attack(n,b):
  p = [2,3,5,7,11,13,17]; i=19; a=2
  while i<b:
    if is_prime(i,10): p.append(i)
    i+=2;
  k = sp.uint64(np.prod(p)); q = power2(a,k,n)
  g = euc_al_i((q-1),n)
  print "product pi: ",k
  print "q: ",q
  print "g: ",g
  #return a

print "pollard_pm1_attack(n,b): ",pollard_pm1_attack(n,2000)

输出未找到p：

Python 2.7 (r27:82525, Jul  4 2010, 09:01:59) [MSC v.1500 32 bit (Intel)] on win32
Type "copyright", "credits" or "license()" for more information.
>>> ================================ RESTART ================================
>>> 
p = 1300199 
q = 2063507 

euler_totient = …

所以我现在正在研究一个java代码.我已经完全正常工作,但是任务的重点是使它分解大数(超过30位).这样做,但它可能需要15分钟才能完成,这是不行的.我的教授向我保证,我使用的算法适用于最多2 ^ 70的数字,并且应该在大约五分钟内完成.我一直试图想出办法(增加2而不是1等),但我似乎无法弄清楚如何在不跳过某些因素的情况下让它更快地移动.有任何想法吗？我还认为Elliptic Curve方法会更好,但他告诉我现在不要处理它.

这是我的代码(ps,sqrt是我自己的函数,但我确信它正在工作):

public String factorizer(BigInteger monster){
    System.out.println("monster =" + monster); 
    String factors = "";  
    BigInteger top = maths.monsterSqrt(monster);   
    if(monster.mod(two).equals(0));
        BigInteger jump = two;
    for(BigInteger bi = two; bi.compareTo(top) <= 0; bi = bi.add(jump)){
        while(monster.mod(bi).equals(zero)){
            factors +=  "+" + bi + ""; 
            monster = monster.divide(bi); 
            jump = one; 
        }
    }
    if(monster.compareTo(BigInteger.ONE) == 1){
        factors  += "+" + monster; 
    } 
    return factors; 
} 

谢谢阅读.一般来说,Javascript和编程都是新手.

我正在寻找一种方法来返回给定数字的最大素数因子.我的第一直觉是使用while循环来计算并查找数字的素数因子,将因子存储在数组中并在每次找到时重置.这样,数组中的最后一项应该是最大的素数因子.

var primerizer = function(input){
    var factors = [];
    var numStorage = input
    for (x=2; numStorage != 1; x++){            // counter stops when the divisor is equal to the last number in the 
                                                // array, meaning the input has been fully factorized
        if (result === 0) {                     // check if the number is prime; if it is not prime
            factors.push(x);                    // add the divisor to the array of prime numbers
            numStorage = numStorage/x           // divide the number being calculated …

我知道已经有一个与此类似的问题，但我想使用 GMPY2（或与 GMP 类似的东西）加快速度。这是我当前的代码，它很不错，但可以更好吗？

编辑：新代码，检查除数 2 和 3

def factors(n):
    result = set()
    result |= {mpz(1), mpz(n)}


    def all_multiples(result, n, factor):
        z = mpz(n)
        while gmpy2.f_mod(mpz(z), factor) == 0:
            z = gmpy2.divexact(z, factor)
            result |= {mpz(factor), z}
        return result

    result = all_multiples(result, n, 2)
    result = all_multiples(result, n, 3)

    for i in range(1, gmpy2.isqrt(n) + 1, 6):
        i1 = mpz(i) + 1
        i2 = mpz(i) + 5
        div1, mod1 = gmpy2.f_divmod(n, i1)
        div2, mod2 = gmpy2.f_divmod(n, i2)
        if mod1 == …

主要是,为什么这么快(对于大数字)？该文档仅告诉我如何使用它.例如,它需要最多一秒才能找到最大的素数因子1234567890987654,对我而言,这似乎是疯狂的.

>>max(factor(1234567890987654))

ans =

    69444443

我想找到范围[1,10 ⁷ ]中所有数字的除数.我知道它可以在O(sqrt(n))中解决.但是在此之前必须运行Eratosthenes的筛子,这可以很容易地修改以获得一个数字的素数因子化(通过跟踪每个数字的一​​个主要因素).所以我想知道使用其素数因子分解生成所有因子会更有效吗？
令n = p ₁ ^{k ₁}*p ₂ ^{k ₂}*....*p _m ^{k _m}

我认为这种表示法可以在O(M +ΣK获得_我)筛后.
经过一番思考后,我想出了以下代码来生成因子:

int factors[]={2,5};        // array containing all the factors
int exponents[]={2,2};      // array containing all the exponents of factors
                            // exponents[i] = exponent of factors[i]
vector <int> ans;           // vector to hold all possible factors

/*
*   stores all possible factors in vector 'ans'
*   using factors and exponents from index l to r(both inclusive)
*/
void gen(int factors[],int …

我需要帮助这个方法的tinyFactor

public static int smallestFactor(int C) 此函数将整数C作为其参数,并返回除C之外的最小整数,即C因子.

参数:C - 要素的整数.

前提条件:C必须大于1.

返回:C的最小因子

public class Factor
{       
public static long smallestFactor(int C)
    {   
    for (int i = 2; i*i<= C; i++) 
    {   
        while (C % i == 0) 
        {
         System.out.print(i + " "); 
         C = C / i;
        }
    }
        return C;
    }
}

我需要找到最小的因子,但我不知道该怎么做