Divisor común aproximado más rápido

13

Visión general

En este desafío, se le darán dos números que son un pequeño desplazamiento mayor que un múltiplo de un número de tamaño mediano. Debe generar un número de tamaño mediano que sea casi un divisor de ambos números, excepto por un pequeño desplazamiento.

El tamaño de los números implicados se puede parametrizar por un parámetro de dificultad, l. Su objetivo es resolver el problema lo más posible len menos de 1 minuto.


Preparar

En un problema dado, habrá un número secreto p, que será un número de bit aleatorio l^2( l*l). Habrá dos multiplicadores, q1, q2que serán l^3números de bits aleatorios , y habrá dos desplazamientos r1, r2, que serán lnúmeros de bits aleatorios .

La entrada a su programa será x1, x2, definida como:

x1 = p * q1 + r1
x2 = p * q2 + r2

Aquí hay un programa para generar casos de prueba, en Python:

from random import randrange
from sys import argv

l = int(argv[1])

def randbits(bits):
    return randrange(2 ** (bits - 1), 2 ** bits)

p = randbits(l ** 2)
print(p)
for i in range(2):
    q_i = randbits(l ** 3)
    r_i = randbits(l)
    print(q_i * p + r_i)

La primera línea de salida es una posible solución, mientras que la segunda y tercera líneas son la entrada que se le dará a su programa.


Su programa

Teniendo en cuenta x1, x2y l, usted debe encontrar un l^2número de bits p'de tal manera que x1 % p'y x2 % p'son ambos lnúmeros de bits. psiempre funcionará, aunque puede haber otras posibilidades. Aquí hay una función para verificar una solución:

def is_correct(x1, x2, l, p_prime):
    p_prime_is_good = p_prime >> (l**2 - 1) and not p_prime >> l ** 2
    x1_is_good = (x1 % p_prime) >> (l-1) and not (x1 % p_prime) >> l
    x2_is_good = (x2 % p_prime) >> (l-1) and not (x2 % p_prime) >> l
    return bool(p_prime_is_good and x1_is_good and x2_is_good)

Ejemplo

Supongamos que les 3. El programa generador elige un número de 9 bits p, que en este caso es 442. El generador elige dos 3números de bit para r1, r2, que son 4, 7. El generador elige dos 27números de bit para q1, q2, que son 117964803, 101808039. Debido a estas opciones, x1, x2son 52140442930, 44999153245.

Su programa se daría 52140442930, 44999153245como entrada, y debe generar un número de 9 bits (en el rango [256, 511]) de modo que 52140442930y el 44999153245módulo ese número dé números de 3 bits (en el rango [4, 7]). 442es el único valor de este tipo en este caso, por lo que su programa tendría que salir 442.


Más ejemplos

l = 2
x1 = 1894
x2 = 2060
p = 11
No other p'.

l = 3
x1 = 56007668599
x2 = 30611458895
p = 424
No other p'.

l = 6
x1 = 4365435975875889219149338064474396898067189178953471159903352227492495111071
x2 = 6466809655659049447127736275529851894657569985804963410176865782113074947167
p = 68101195620
I don't know whether there are other p'.

l = 12
x1 = 132503538560485423319724633262218262792296147003813662398252348727558616998821387759658729802732555377599590456096450977511271450086857949046098328487779612488702544062780731169071526325427862701033062986918854245283037892816922645703778218888876645148150396130125974518827547039720412359298502758101864465267219269598121846675000819173555118275197412936184329860639224312426860362491131729109976241526141192634523046343361089218776687819810873911761177080056675776644326080790638190845283447304699879671516831798277084926941086929776037986892223389603958335825223
x2 = 131643270083452525545713630444392174853686642378302602432151533578354175874660202842105881983788182087244225335788180044756143002547651778418104898394856368040582966040636443591550863800820890232349510212502022967044635049530630094703200089437589000344385691841539471759564428710508659169951391360884974854486267690231936418935298696990496810984630182864946252125857984234200409883080311780173125332191068011865349489020080749633049912518609380810021976861585063983190710264511339441915235691015858985314705640801109163008926275586193293353829677264797719957439635
p = 12920503469397123671484716106535636962543473
I don't know whether there are other p'.

l = 12
x1 = 202682323504122627687421150801262260096036559509855209647629958481910539332845439801686105377638207777951377858833355315514789392768449139095245989465034831121409966815913228535487871119596033570221780568122582453813989896850354963963579404589216380209702064994881800638095974725735826187029705991851861437712496046570494304535548139347915753682466465910703584162857986211423274841044480134909827293577782500978784365107166584993093904666548341384683749686200216537120741867400554787359905811760833689989323176213658734291045194879271258061845641982134589988950037
x2 = 181061672413088057213056735163589264228345385049856782741314216892873615377401934633944987733964053303318802550909800629914413353049208324641813340834741135897326747139541660984388998099026320957569795775586586220775707569049815466134899066365036389427046307790466751981020951925232623622327618223732816807936229082125018442471614910956092251885124883253591153056364654734271407552319665257904066307163047533658914884519547950787163679609742158608089946055315496165960274610016198230291033540306847172592039765417365770579502834927831791804602945514484791644440788
p = 21705376375228755718179424140760701489963164

Puntuación

Como se mencionó anteriormente, el puntaje de su programa es el más alto lque el programa completa en menos de 1 minuto. Más específicamente, su programa se ejecutará en 5 instancias aleatorias con eso l, y debe generar una respuesta correcta en los 5, con un tiempo promedio inferior a 1 minuto. El puntaje de un programa será el más alto en el lque tenga éxito. Tiebreaker será el tiempo promedio en eso l.

Para darle una idea de a qué puntajes apuntar, escribí un solucionador de fuerza bruta muy simple. Obtuve un puntaje de 5. Escribí un solucionador mucho más elegante. Obtuvo una puntuación de 12 o 13, dependiendo de la suerte.


Detalles

Para una comparación perfecta entre las respuestas, programaré las presentaciones en mi computadora portátil para obtener puntajes canónicos. También ejecutaré las mismas instancias elegidas al azar en todas las presentaciones, para aliviar un poco la suerte. Mi computadora portátil tiene 4 CPU, CPU i5-4300U a 1.9 GHz, 7.5G de RAM.

Siéntase libre de publicar un puntaje provisional basado en su propio tiempo, solo deje en claro si es provisional o canónico.


¡Que gane el programa más rápido!

isaacg
fuente
¿La aproximación tiene que ser la más cercana?
Yytsi
@TuukkaX Cualquier l^2número de bit que esté l-bits lejos de ser un factor de ambos números funciona. Sin embargo, generalmente solo hay uno.
isaacg
Aquí hay una disertación con algunas ideas de algoritmos: tigerprints.clemson.edu/cgi/… . Particularmente agradable y simple es el de la sección 5.1.1
isaacg
El i5-4300U tiene 2 núcleos (4 hilos), no 4 núcleos.
Anders Kaseorg

Respuestas:

3

Óxido, L = 13

src/main.rs

extern crate gmp;
extern crate rayon;

use gmp::mpz::Mpz;
use gmp::rand::RandState;
use rayon::prelude::*;
use std::cmp::max;
use std::env;
use std::mem::swap;

// Solver

fn solve(x1: &Mpz, x2: &Mpz, l: usize) -> Option<Mpz> {
    let m = l*l - 1;
    let r = -1i64 << l-2 .. 1 << l-2;
    let (mut x1, mut x2) = (x1 - (3 << l-2), x2 - (3 << l-2));
    let (mut a1, mut a2, mut b1, mut b2) = (Mpz::one(), Mpz::zero(), Mpz::zero(), Mpz::one());
    while !x2.is_zero() &&
        &(max(a1.abs(), b1.abs()) << l-2) < &x1 &&
        &(max(a2.abs(), b2.abs()) << l-2) < &x2
    {
        let q = &x1/&x2;
        swap(&mut x1, &mut x2);
        x2 -= &q*&x1;
        swap(&mut a1, &mut a2);
        a2 -= &q*&a1;
        swap(&mut b1, &mut b2);
        b2 -= &q*&b1;
    }
    r.clone().into_par_iter().map(|u| {
        let (mut y1, mut y2) = (&x1 - &a1*u + (&b1 << l-2), &x2 - &a2*u + (&b2 << l-2));
        for _ in r.clone() {
            let d = Mpz::gcd(&y1, &y2);
            if d.bit_length() >= m {
                let d = d.abs();
                let (mut k, k1) = (&d >> l*l, &d >> l*l-1);
                while k < k1 {
                    k += 1;
                    if (&d%&k).is_zero() {
                        return Some(&d/&k)
                    }
                }
            }
            y1 -= &b1;
            y2 -= &b2;
        }
        None
    }).find_any(|o| o.is_some()).unwrap_or(None)
}

// Test harness

fn randbits(rnd: &mut RandState, bits: usize) -> Mpz {
    rnd.urandom(&(Mpz::one() << bits - 1)) + (Mpz::one() << bits - 1)
}

fn gen(rnd: &mut RandState, l: usize) -> (Mpz, Mpz, Mpz) {
    let p = randbits(rnd, l*l);
    (randbits(rnd, l*l*l)*&p + randbits(rnd, l),
     randbits(rnd, l*l*l)*&p + randbits(rnd, l),
     p)
}

fn is_correct(x1: &Mpz, x2: &Mpz, l: usize, p_prime: &Mpz) -> bool {
    p_prime.bit_length() == l*l &&
        (x1 % p_prime).bit_length() == l &&
        (x2 % p_prime).bit_length() == l
}

fn random_test(l: usize, n: usize) {
    let mut rnd = RandState::new();  // deterministic seed
    for _ in 0..n {
        let (x1, x2, p) = gen(&mut rnd, l);
        println!("x1 = {}", x1);
        println!("x2 = {}", x2);
        println!("l = {}", l);
        println!("p = {}", p);
        println!("x1 % p = {}", &x1 % &p);
        println!("x2 % p = {}", &x2 % &p);
        assert!(is_correct(&x1, &x2, l, &p));
        let p_prime = solve(&x1, &x2, l).expect("no solution found!");
        println!("p' = {}", p_prime);
        assert!(is_correct(&x1, &x2, l, &p_prime));
        println!("correct");
    }
}

// Command line interface

fn main() {
    let args = &env::args().collect::<Vec<_>>();
    if args.len() == 4 && args[1] == "--random" {
        if let (Ok(l), Ok(n)) = (args[2].parse(), args[3].parse()) {
            return random_test(l, n);
        }
    }
    if args.len() == 4 {
        if let (Ok(x1), Ok(x2), Ok(l)) = (args[1].parse(), args[2].parse(), args[3].parse()) {
            match solve(&x1, &x2, l) {
                None => println!("no solution found"),
                Some(p_prime) => println!("{}", p_prime),
            }
            return;
        }
    }
    println!("Usage:");
    println!("    {} --random L N", args[0]);
    println!("    {} X1 X2 L", args[0]);
}

Cargo.toml

[package]
name = "agcd"
version = "0.1.0"
authors = ["Anders Kaseorg <[email protected]>"]

[dependencies]
rayon = "0.7.1"
rust-gmp = "0.5.0"

Correr

cargo build --release
target/release/agcd 56007668599 30611458895 3
target/release/agcd --random 13 5
Anders Kaseorg
fuente
El resultado oficial es l = 13, con un tiempo promedio de 41.53s. l = 14 tomó un poco más de 2m en promedio.
isaacg 01 de
2

Mathematica, L = 5

Aquí hay una solución rápida 5

(l = #3;
a = #1 - Range[2^(l - 1), 2^l];
b = #2 - Range[2^(l - 1), 2^l];
Last@Intersection[
Flatten[Table[Select[Divisors@a[[i]], # < 2^l^2 &], {i, Length@a}],
 1],
Flatten[Table[Select[Divisors@b[[i]], # < 2^l^2 &], {i, Length@b}],
 1]]
) &

Entrada
[x1, x2, L]

para que cualquiera pueda probar esto, aquí está el generador de claves

l = 5;
a = RandomInteger[{2^(l^2 - 1), 2^(l^2)}]
b = RandomInteger[{2^(l^3 - 1), 2^(l^3)}];
c = RandomInteger[{2^(l - 1), 2^l - 1}];
f = RandomInteger[{2^(l^3 - 1), 2^(l^3)}];
g = RandomInteger[{2^(l - 1), 2^l - 1}];
x = a*b + c
y = a*f + g

elija el valor L ejecutado, el código y obtendrá tres números.
coloca los dos últimos junto con L como entrada, y deberías obtener el primero

J42161217
fuente
Verifiqué que esta solución obtuviera una puntuación de l = 5. Lo cronometraré si se necesita tiempo como un desempate.
isaacg
1

Mathematica, L = 12

ClearAll[l, a, b, k, m];
(l = #3;
a = #1 - Range[2^(l - 1), 2^l];
b = #2 - Range[2^(l - 1), 2^l];
k = Length@a;
m = Length@b;
For[i = 1, i <= k, i++, 
For[j = 1, j <= m, j++, If[2^(l^2 - 1) < GCD[a[[i]], b[[j]]],
 If[GCD[a[[i]], b[[j]]] > 2^l^2, 
  Print@Max@
    Select[Divisors[GCD[a[[i]], b[[j]]]], 
     2^(l^2 - 1) < # < 2^l^2 &]; Abort[], 
  Print[GCD[a[[i]], b[[j]]]];
  Abort[]]]]]) &

entrada [x1, x2, L]

para que cualquiera pueda probar esto, aquí está el generador de claves

l = 12;
a = RandomInteger[{2^(l^2 - 1), 2^(l^2)}]
b = RandomInteger[{2^(l^3 - 1), 2^(l^3)}];
c = RandomInteger[{2^(l - 1), 2^l - 1}];
f = RandomInteger[{2^(l^3 - 1), 2^(l^3)}];
g = RandomInteger[{2^(l - 1), 2^l - 1}];
x = a*b + c
y = a*f + g

elige el valor L, ejecuta el código y obtendrás tres números.
coloca los dos últimos junto con L como entrada, y deberías obtener el primero

J42161217
fuente
Cuando probé esto con l = 12, dio un resultado incorrecto. Específicamente, el divisor resultante fue un número de 146 bits, que es demasiado grande. Creo que solo necesitarás un pequeño cambio para arreglar esto.
isaacg
Agregué el caso erróneo como el ejemplo final anterior. Su solucionador le dio una respuesta igual a 3 * p, que era un poco demasiado grande. Al mirar su código, parece que solo verifica que su salida tiene al menos l^2bits, pero también necesita verificar que tenga la mayoría de los l^2bits.
isaacg
En el mismo caso de prueba que falló antes, todavía no funciona. No estoy muy familiarizado con Mathematica, pero parecía que salió sin salida. Creo que el problema es que está encontrando un factor que es demasiado grande, y luego, en lugar de encontrar un divisor del factor en el rango deseado, simplemente lo está pasando.
isaacg
Continuemos esta discusión en el chat .
isaacg 01 de
El puntaje oficial es L = 12, con un tiempo promedio de 52.7s. ¡Bien hecho!
isaacg 01 de
1

Python, L = 15, tiempo promedio 39.9s

from sys import argv
from random import seed, randrange

from gmpy2 import gcd, mpz
import gmpy2

def mult_buckets(buckets):
    if len(buckets) == 1:
        return buckets[0]
    new_buckets = []
    for i in range(0, len(buckets), 2):
        if i == len(buckets) - 1:
            new_buckets.append(buckets[i])
        else:
            new_buckets.append(buckets[i] * buckets[i+1])
    return mult_buckets(new_buckets)


def get_products(xs, l):
    num_buckets = 1000
    lower_r = 1 << l - 1
    upper_r = 1 << l
    products = []
    bucket_size = (upper_r - lower_r)//num_buckets + 1
    for x in xs:
        buckets = []
        for bucket_num in range(num_buckets):
            product = mpz(1)
            for r in range(lower_r + bucket_num * bucket_size,
                           min(upper_r, lower_r + (bucket_num + 1) * bucket_size)):
                product *= x - mpz(r)
            buckets.append(product)
        products.append(mult_buckets(buckets))
    return products

def solve(xs, l):
    lower_r = 2**(l - 1)
    upper_r = 2**l
    lower_p = 2**(l**2 - 1)
    upper_p = 2**(l**2)

    products = get_products(xs, l)
    overlap = gcd(*products)
    candidate_lists = []
    for x in xs:
        candidates = []
        candidate_lists.append(candidates)
        for r in range(lower_r, upper_r):
            common_divisor = gcd(x-r, overlap)
            if common_divisor >= lower_p:
                candidates.append(common_divisor)
    to_reduce = []
    for l_candidate in candidate_lists[0]:
        for r_candidate in candidate_lists[1]:
            best_divisor = gcd(l_candidate, r_candidate)
            if lower_p <= best_divisor < upper_p:
                return best_divisor
            elif best_divisor > upper_p:
                to_reduce.append(best_divisor)
    for divisor in to_reduce:
        cutoff = divisor // lower_p
        non_divisors = []
        for sub_divisor in range(2, cutoff + 1):
            if any(sub_divisor % non_divisor == 0 for non_divisor in non_divisors):
                continue
            quotient, remainder = gmpy2.c_divmod(divisor, sub_divisor)
            if remainder == 0 and lower_p <= quotient < upper_p:
                return quotient
            if quotient < lower_p:
                break
            if remainder != 0:
                non_divisors.append(sub_divisor)

def is_correct(x1, x2, l, p_prime):
    p_prime_is_good = p_prime >> (l**2 - 1) and not p_prime >> l ** 2
    x1_is_good = (x1 % p_prime) >> (l-1) and not (x1 % p_prime) >> l
    x2_is_good = (x2 % p_prime) >> (l-1) and not (x2 % p_prime) >> l
    return bool(p_prime_is_good and x1_is_good and x2_is_good)

if __name__ == '__main__':
    seed(0)

    l = int(argv[1])
    reps = int(argv[2])

    def randbits(bits):
        return randrange(2 ** (bits - 1), 2 ** bits)

    for _ in range(reps):
        p = randbits(l ** 2)
        print("p = ", p)
        xs = []
        for i in range(2):
            q_i = randbits(l ** 3)
            print("q", i, "=", q_i)
            r_i = randbits(l)
            print("r", i, "=", r_i)
            x_i = q_i * p + r_i
            print("x", i, "=", x_i)
            xs.append(x_i)

        res = solve(xs, l)
        print("answer = ", res)
        print("Correct?", is_correct(xs[0], xs[1], l, res))

Este código se basa en el hecho de que el producto de x1 - r para todos los valores posibles de r debe ser un múltiplo de p, y el producto de x2 - r también debe serlo. La mayor parte del tiempo se dedica a tomar el mcd de los dos productos, cada uno de los cuales tiene aproximadamente 60,000,000 bits. El mcd, que solo tiene alrededor de 250,000 bits, se compara con cada uno de los valores xr una vez más, para extraer los candidatos p '. Si son demasiado grandes, la división de prueba se usa para reducirlos al rango apropiado.

Esto se basa en la biblioteca gmpy2 para Python, que es un envoltorio delgado para la biblioteca GNU MP, que en particular tiene una rutina gcd realmente buena.

Este código es de un solo subproceso.

isaacg
fuente