Rust `find_any`继续搜索

e4yzc0pl  于 2023-08-05  发布在  其他
关注(0)|答案(1)|浏览(115)

我正试图用蛮力从g^x = y (mod p)中找到x，因为我知道x只有“几个”位。

  1. use num_bigint::BigUint;
  2. use num_traits::One;
  3. use rayon::prelude::*;
  4. use std::sync::Mutex;
  6. fn main() {
  7.     let p = BigUint::parse_bytes("531137992816767098689588206552468627329593117727031923199444138200403559860852242739162502265229285668889329486246501015346579337652707239409519978766587351943831270835393219031728127"
  8.         .as_bytes(), 10).unwrap();
  9.     let g = BigUint::parse_bytes("743488989946216334211646350465118756727157777337013657445667148279632819469843031446430723942629760903918287800011367316376"
  10.         .as_bytes(), 10).unwrap();
  11.     let y = BigUint::parse_bytes("85300193795644893333630947242400469685524126293619036977651049331711403849653080708338436527820826037193273430333874138094661788038445049976895820193634304228963983382234907450594225"
  12.         .as_bytes(), 10).unwrap();
  14.     println!("g: {}", g);
  15.     println!("y: {}", y);
  17.     // Brute force y = g^x
  18.     let size = BigUint::from(2u32).pow(20);
  19.     let num_cores = 8 as usize;
  20.     let chunk_size = &size / num_cores;
  22.     let num = Mutex::new(None);
  23.     (0..num_cores)
  24.         .into_par_iter()
  25.         .find_any(|&core_idx| {
  26.             let start = chunk_size.clone() * core_idx;
  27.             let end = if core_idx == num_cores - 1 {
  28.                 size.clone()
  29.             } else {
  30.                 start.clone() + chunk_size.clone()
  31.             };
  33.             let mut x = start.clone();
  34.             while x < end {
  35.                 let y_candidate = g.modpow(&x, &p);
  37.                 // Check if g^x == y
  38.                 if y_candidate == y {
  39.                     println!("Found x: {}", x);
  40.                     *num.lock().unwrap() = Some(x.clone());
  42.                     return true;
  43.                 }
  45.                 x += BigUint::one();
  46.             }
  48.             false
  49.         });
  51.     if let Some(x) = num.lock().unwrap().clone() {
  52.         println!("Found num: {}", x);
  54.     } else {
  55.         println!("x not found in the specified range.");
  56.     };
  57. }

字符串
我面临的问题是，尽管一个线程找到了x，但其余的线程仍在继续搜索。我猜find_any不能保证其他线程会停止。有什么建议可以优化一下吗？资料来源：
“在并行迭代器中搜索与给定 predicate 匹配的某个项并返回它。这个操作类似于在顺序迭代器上查找，但是返回的项可能不是并行序列中第一个匹配的项，因为我们并行搜索整个序列。
一旦找到匹配项，我们将尝试尽快停止处理迭代器中的其余项（就像find一旦找到匹配项就停止迭代一样）”

rust

1条答案

按热度按时间
qgelzfjb

qgelzfjb1#

这可以通过直接并行迭代搜索范围来简化，只要您的最大x值适合u64甚至u128。

（1）简单并行

  1. use num_bigint::BigUint;
  2. use num_traits::One;
  3. use rayon::prelude::*;
  4. use std::sync::Mutex;
  6. fn main() {
  7.     let p = BigUint::parse_bytes("531137992816767098689588206552468627329593117727031923199444138200403559860852242739162502265229285668889329486246501015346579337652707239409519978766587351943831270835393219031728127"
  8.         .as_bytes(), 10).unwrap();
  9.     let g = BigUint::parse_bytes("743488989946216334211646350465118756727157777337013657445667148279632819469843031446430723942629760903918287800011367316376"
  10.         .as_bytes(), 10).unwrap();
  11.     let y = BigUint::parse_bytes("85300193795644893333630947242400469685524126293619036977651049331711403849653080708338436527820826037193273430333874138094661788038445049976895820193634304228963983382234907450594225"
  12.         .as_bytes(), 10).unwrap();
  14.     println!("g: {}", g);
  15.     println!("y: {}", y);
  17.     // Brute force y = g^x
  18.     let size = 2_u64.pow(20);
  20.     let num = (0..size)
  21.         .into_par_iter()
  22.         .map(|n| BigUint::from(n))
  23.         .find_any(|x| {
  24.             let y_candidate = g.modpow(&x, &p);
  26.             // Check if g^x == y
  27.             if y_candidate == y {
  28.                 println!("Found x: {}", x);
  29.                 true
  30.             } else {
  31.                 false
  32.             }
  33.         });
  35.     if let Some(x) = num.clone() {
  36.         println!("Found num: {}", x);
  37.     } else {
  38.         println!("x not found in the specified range.");
  39.     };
  40. }

字符串
playground

（2）分块处理

但是将计算分块可能会更有性能。而不是像你所做的那样每个核心一个块，使用一个足够小的块大小，这样就不会太明显：

  1. use num_bigint::BigUint;
  2. use rayon::prelude::*;
  4. fn main() {
  5.     let p = BigUint::parse_bytes("531137992816767098689588206552468627329593117727031923199444138200403559860852242739162502265229285668889329486246501015346579337652707239409519978766587351943831270835393219031728127"
  6.         .as_bytes(), 10).unwrap();
  7.     let g = BigUint::parse_bytes("743488989946216334211646350465118756727157777337013657445667148279632819469843031446430723942629760903918287800011367316376"
  8.         .as_bytes(), 10).unwrap();
  9.     let y = BigUint::parse_bytes("85300193795644893333630947242400469685524126293619036977651049331711403849653080708338436527820826037193273430333874138094661788038445049976895820193634304228963983382234907450594225"
  10.         .as_bytes(), 10).unwrap();
  12.     println!("g: {}", g);
  13.     println!("y: {}", y);
  15.     // Brute force y = g^x
  16.     let size = BigUint::from(2_u32).pow(20);
  17.     let min_chunk_size: usize = 1000;
  19.     // Ensure that we don't have more than `usize::MAX` chunks
  20.     let chunk_size = (&size / usize::MAX).max(BigUint::from(min_chunk_size));
  21.     let chunk_count: usize = (&size / &chunk_size).try_into().unwrap();
  23.     let num = (0..chunk_count)
  24.         .into_par_iter()
  25.         .find_map_any(|chunk| {
  26.             let start = &chunk_size * chunk;
  27.             let end = if chunk + 1 == chunk_count {
  28.                 size.clone()
  29.             } else {
  30.                 &start + &chunk_size
  31.             };
  33.             let mut x = start;
  34.             while x < end {
  35.                 let y_candidate = g.modpow(&x, &p);
  37.                 // Check if g^x == y
  38.                 if y_candidate == y {
  39.                     println!("Found x: {}", x);
  40.                     return Some(x);
  41.                 }
  43.                 x += 1_u8;
  44.             }
  46.             None
  47.         });
  49.     if let Some(x) = num.clone() {
  50.         println!("Found num: {}", x);
  51.     } else {
  52.         println!("x not found in the specified range.");
  53.     };
  54. }

型
playground
这也允许您将size设置为BigUint，这意味着您的x范围是无限的。但是如果size > usize::MAX * 1000，块大小（以及找到答案后的延迟）将开始增加。

（3）原子标志

您可以在找到答案时设置原子，并在循环中检查该原子。这允许您几乎立即停止，即使是非常大的块大小。

  1. use std::sync::atomic::{AtomicBool, Ordering};
  2. use num_bigint::BigUint;
  3. use rayon::prelude::*;
  5. fn main() {
  6.     let p = BigUint::parse_bytes("531137992816767098689588206552468627329593117727031923199444138200403559860852242739162502265229285668889329486246501015346579337652707239409519978766587351943831270835393219031728127"
  7.         .as_bytes(), 10).unwrap();
  8.     let g = BigUint::parse_bytes("743488989946216334211646350465118756727157777337013657445667148279632819469843031446430723942629760903918287800011367316376"
  9.         .as_bytes(), 10).unwrap();
  10.     let y = BigUint::parse_bytes("85300193795644893333630947242400469685524126293619036977651049331711403849653080708338436527820826037193273430333874138094661788038445049976895820193634304228963983382234907450594225"
  11.         .as_bytes(), 10).unwrap();
  13.     println!("g: {}", g);
  14.     println!("y: {}", y);
  16.     // Brute force y = g^x
  17.     let zero = BigUint::from(0_u32);
  18.     let size = BigUint::from(2_u32).pow(20);
  19.     let chunk_count: usize = 8;
  20.     let chunk_size = &size / &chunk_count;
  22.     let found = AtomicBool::new(false);
  24.     let num = (0..chunk_count)
  25.         .into_par_iter()
  26.         .find_map_any(|chunk| {
  27.             let start = &chunk_size * chunk;
  28.             let end = if chunk + 1 == chunk_count {
  29.                 size.clone()
  30.             } else {
  31.                 &start + &chunk_size
  32.             };
  34.             let mut x = start;
  35.             while x < end {
  36.                 // Stop if the answer was found
  37.                 // Check infrequently to as to amortize the atomic read
  38.                 if &x % 100_u32 == zero {
  39.                     if found.load(Ordering::Relaxed) {
  40.                         break;
  41.                     }
  42.                 }
  44.                 let y_candidate = g.modpow(&x, &p);
  46.                 // Check if g^x == y
  47.                 if y_candidate == y {
  48.                     println!("Found x: {}", x);
  49.                     found.store(true, Ordering::Relaxed);
  50.                     return Some(x);
  51.                 }
  53.                 x += 1_u8;
  54.             }
  56.             None
  57.         });
  59.     if let Some(x) = num.clone() {
  60.         println!("Found num: {}", x);
  61.     } else {
  62.         println!("x not found in the specified range.");
  63.     };
  64. }

型
playground的
如果您期望答案接近范围的开始，我建议使用比处理核心多得多的块。这可以防止在与答案相距甚远的块上浪费太多的处理能力。

展开查看全部
赞(0）分享  回复(0）举报  2023-08-05
我来回答

相关问题

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新问答

    更多
    • 蜀ICP备13028337号-1 大数据知识库 https://www.saoniuhuo.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com