API tools faq
paste
Advertisement
Nickpips

BigInt

Nickpips
Nov 4th, 2018
134
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Rust 20.41 KB | None | 0 0
raw download clone embed print report
  1. #![feature(trace_macros)]
  2.  
  3. use std::ops;
  4. use std::fmt;
  5. use std::cmp;
  6.  
  7. #[derive(Clone)]
  8. struct BigUInt {
  9.     val : Vec<u128>,
  10. }
  11.  
  12. fn sgn(i: i128) -> i8 {
  13.     if i == 0 {
  14.         0
  15.     } else if i < 0 {
  16.         -1
  17.     } else {
  18.         1
  19.     }
  20. }
  21.  
  22. impl BigUInt {
  23.     fn new(v: u128) -> BigUInt {
  24.         BigUInt {
  25.             val : vec![v],
  26.         }
  27.     }
  28.     fn parse_hex(hex: String) -> BigUInt {
  29.         let mut ret = Vec::new();
  30.         ret.resize(hex.len() * 4 / 128 + 1, 0);
  31.         let mut pos = 0;
  32.         for i in hex.bytes().rev() {
  33.             let mut byte = i - 48;
  34.             if byte > 10 {
  35.                 byte = i - 65 + 10;
  36.             }
  37.             let batch = pos / 128;
  38.             let shift = pos % 128;
  39.             ret[batch] |= (byte as u128) << shift;
  40.             pos += 4;
  41.         }
  42.         let mut len = ret.len();
  43.         while len > 1 && ret[len - 1] == 0 {
  44.             len -= 1;
  45.         }
  46.         ret.resize(len, 0);
  47.         BigUInt {
  48.             val: ret,
  49.         }
  50.     }
  51.     fn num_bits(&self) -> usize {
  52.         while self.val[0] == 0 && self.val.len() == 1 {
  53.             return 0;
  54.         }
  55.         let mut bit = 127;
  56.         let last = self.val.len() - 1;
  57.         while ((self.val[last] >> bit) & 1) == 0 {
  58.             bit -= 1;
  59.         }
  60.         bit
  61.     }
  62.     fn getBit(&self, i: usize) -> bool {
  63.         let batch = i / 128;
  64.         if batch >= self.val.len() {
  65.             false
  66.         } else {
  67.             if self.val[batch] & (1u128 << i % 128) == 0 {
  68.                 false
  69.             } else {
  70.                 true
  71.             }
  72.         }
  73.     }
  74.     fn sq(&self) -> BigUInt {
  75.         self * self
  76.     }
  77.     fn pow(&self, pow: &BigUInt) -> BigUInt {
  78.         let mut sq = self.clone();
  79.         let mut ret = BigUInt::new(1);
  80.         let num_bits = pow.num_bits();
  81.         for i in 0..num_bits + 1 {
  82.             if ((pow.val[i / 128] >> (i % 128)) & 1) == 1 {
  83.                 ret = &ret * &sq;
  84.             }
  85.             if i < num_bits {
  86.                 sq = &sq * &sq;
  87.             }
  88.         }
  89.         ret
  90.     }
  91.     fn powmod(&self, pow: &BigUInt, modulus: &BigUInt) -> BigUInt {
  92.         let mut sq = self.clone();
  93.         let mut ret = BigUInt::new(1);
  94.         let num_bits = pow.num_bits();
  95.         for i in 0..num_bits + 1 {
  96.             if ((pow.val[i / 128] >> (i % 128)) & 1) == 1 {
  97.                 ret = &ret * &sq;
  98.             }
  99.             if i < num_bits {
  100.                 sq = &sq * &sq;
  101.                 if &sq >= modulus {
  102.                     sq = &sq % &modulus;
  103.                 }
  104.             }
  105.         }
  106.         &ret % &modulus
  107.     }
  108. }
  109.  
  110. impl fmt::Display for BigUInt {
  111.     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
  112.         //let mut out : Vec<u8> = Vec::new();
  113.         let mut rest = self.clone();
  114.         let zero = BigUInt::new(0);
  115.         let ten = BigUInt::new(10);
  116.         if rest == zero {
  117.             write!(f, "0")
  118.         } else {
  119.             let mut digits = Vec::new();
  120.             while rest > zero {
  121.                 let digit = &rest % &ten;
  122.                 digits.push(digit.val[0] as u8 + 48);
  123.                 rest = &rest / &ten;
  124.             }
  125.             digits.reverse();
  126.             write!(f, "{}", String::from_utf8(digits).unwrap())
  127.         }
  128.     }
  129. }
  130.  
  131. impl fmt::Binary for BigUInt {
  132.     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
  133.         for i in self.val.iter().rev() {
  134.             write!(f, "{:0128b}", i)?;
  135.         }
  136.         write!(f, "")
  137.     }
  138. }
  139.  
  140. impl fmt::Debug for BigUInt {
  141.     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
  142.         for i in self.val.iter().rev() {
  143.             write!(f, "{:0128b}", i)?;
  144.         }
  145.         write!(f, "")
  146.     }
  147. }
  148.  
  149. impl cmp::Ord for BigUInt {
  150.     fn cmp(&self, other: &BigUInt) -> cmp::Ordering {
  151.         let mut len_cmp = (&self.val.len()).cmp(&other.val.len());
  152.         if len_cmp == cmp::Ordering::Equal {
  153.             let mut len = self.val.len();
  154.             while len > 0 && len_cmp == cmp::Ordering::Equal {
  155.                 len_cmp = self.val[len - 1].cmp(&other.val[len - 1]);
  156.                 len -= 1;
  157.             }
  158.         }
  159.         len_cmp
  160.     }
  161. }
  162.  
  163. impl cmp::Eq for BigUInt {}
  164.  
  165. impl cmp::PartialOrd for BigUInt {
  166.     fn partial_cmp(&self, other: &BigUInt) -> Option<cmp::Ordering> {
  167.         Some(self.cmp(other))
  168.     }
  169. }
  170.  
  171. impl cmp::PartialEq for BigUInt {
  172.     fn eq(&self, other: &BigUInt) -> bool {
  173.         self.cmp(other) == cmp::Ordering::Equal
  174.     }
  175. }
  176.  
  177. macro_rules! implBigUIntFrom {
  178.     ($originType:ty) => {
  179.         impl From<$originType> for BigUInt {
  180.             fn from(v : $originType) -> BigUInt {
  181.                 BigUInt::new(v as u128)
  182.             }
  183.         }
  184.     };
  185. }
  186.  
  187. implBigUIntFrom!(u8);
  188. implBigUIntFrom!(u16);
  189. implBigUIntFrom!(u32);
  190. implBigUIntFrom!(u64);
  191. implBigUIntFrom!(u128);
  192. implBigUIntFrom!(i8);
  193. implBigUIntFrom!(i16);
  194. implBigUIntFrom!(i32);
  195. implBigUIntFrom!(i64);
  196. implBigUIntFrom!(i128);
  197.  
  198. fn smaller<'a>(v1 : &'a Vec<u128>, v2 : &'a Vec<u128>) -> (&'a Vec<u128>, &'a Vec<u128>) {
  199.    if v1.len() < v2.len() {
  200.        (v1, v2)
  201.    } else {
  202.        (v2, v1)
  203.    }
  204. }
  205.  
  206. macro_rules! toVal {
  207.    (@parsing ($($stack:tt)*) R $($rest:tt)*) => {
  208.        {
  209.            toVal!(@parsing (* $($stack)*) $($rest)*)
  210.        }
  211.    };
  212.    (@parsing ($($stack:tt)*) $($rest:tt)*) => {
  213.        {
  214.            $($stack)*
  215.        }
  216.    };
  217.    ($first:expr, $($rest:tt)*) => {
  218.        {
  219.            toVal!(@parsing ($first) $($rest)*)
  220.        }
  221.    };
  222. }
  223.  
  224. macro_rules! implBigUIntAdd {
  225.    ($lhsType:ty, $rhsType:ty, $($lhsRefs:ident)*, $($rhsRefs:ident)*, $($generics:tt)*) => {
  226.        impl$($generics)* ops::Add<$rhsType> for $lhsType {
  227.            type Output = BigUInt;
  228.            
  229.            fn add(self, rhs: $rhsType) -> BigUInt {
  230.                let ord = smaller(&self.val, &rhs.val);
  231.                let mut ret = Vec::new();
  232.                ret.resize(ord.1.len() + 1, 0);
  233.                let mut carry = false;
  234.                for i in 0..ord.0.len() {
  235.                    let mut res = ord.0[i].overflowing_add(ord.1[i]);
  236.                    ret[i] = res.0;
  237.                    if carry {
  238.                        if !ret[i] == 0 {
  239.                            if res.1 {
  240.                                panic!("Double Carry!");
  241.                            }
  242.                            ret[i] = 0;
  243.                            res.1 = true;
  244.                        } else {
  245.                            ret[i] += 1;
  246.                        }
  247.                    }
  248.                    carry = res.1;
  249.                }
  250.                let mut real_len = ord.0.len();
  251.                if ord.0.len() != ord.1.len() {
  252.                    for i in ord.0.len()..ord.1.len() {
  253.                        ret[i] = ord.1[i];
  254.                        if carry {
  255.                            if !ret[i] == 0 {
  256.                                ret[i] = 0;
  257.                                carry = true;
  258.                            } else {
  259.                                ret[i] += 1;
  260.                                carry = false;
  261.                            }
  262.                        } else {
  263.                            carry = false;
  264.                        }
  265.                        if ret[i] != 0 {
  266.                            real_len = cmp::max(real_len, i + 1);
  267.                        }
  268.                    }
  269.                }
  270.                if carry {
  271.                    ret[ord.1.len()] += 1;
  272.                } else {
  273.                    ret.resize(real_len, 0);
  274.                }
  275.                if ret.len() > 1 && ret[ret.len() - 1] == 0 {
  276.                    panic!("Invalid len at add!");
  277.                }
  278.                debug_assert!(ret.len() == 1 || ret[ret.len() - 1] != 0);
  279.                BigUInt {
  280.                    val: ret,
  281.                }
  282.            }
  283.        }
  284.    };
  285. }
  286.  
  287. macro_rules! implBigUIntSub {
  288.    ($lhsType:ty, $rhsType:ty, $($lhsRefs:ident)*, $($rhsRefs:ident)*, $($generics:tt)*) => {
  289.        impl$($generics)* ops::Sub<$rhsType> for $lhsType {
  290.            type Output = BigUInt;
  291.            
  292.            fn sub(self, rhs: $rhsType) -> BigUInt {
  293.                if toVal!(&rhs, $($rhsRefs)*) > toVal!(&self, $($lhsRefs)*) {
  294.                    panic!("Subtracting the wrong way!");
  295.                }
  296.                let mut subtrahend_buf = rhs.val.clone();
  297.                let mut len = self.val.len() + 1;
  298.                subtrahend_buf.resize(len, 0);
  299.                for i in subtrahend_buf.iter_mut() {
  300.                    *i = !*i;
  301.                }
  302.                let subtrahend = BigUInt {
  303.                    val: subtrahend_buf,
  304.                };
  305.                let mut ret = self + &subtrahend + BigUInt::new(1);
  306.                ret.val[len] -= 1;
  307.                while len > 1 && ret.val[len - 1] == 0 {
  308.                    len -= 1;
  309.                }
  310.                ret.val.resize(len, 0);
  311.                debug_assert!(ret.val.len() == 1 || ret.val[ret.val.len() - 1] != 0);
  312.                ret
  313.            }
  314.        }
  315.    };
  316. }
  317.  
  318. macro_rules! implBigUIntMul {
  319.    ($lhsType:ty, $rhsType:ty, $($lhsRefs:ident)*, $($rhsRefs:ident)*, $($generics:tt)*) => {
  320.        impl$($generics)* ops::Mul<$rhsType> for $lhsType {
  321.            type Output = BigUInt;
  322.            
  323.            fn mul(self, rhs: $rhsType) -> BigUInt {
  324.                const LOWER_MASK : u128 = !0u64 as u128;
  325.                let mut ret : Vec<u128> = Vec::new();
  326.                let len = self.val.len() + rhs.val.len();
  327.                ret.resize(3 * len, 0);
  328.                let ord = smaller(&self.val, &rhs.val);
  329.                for i in 0..ord.0.len()*2 {
  330.                    for j in 0..ord.1.len()*2 {
  331.                        let mut x = ord.0[i >> 1];
  332.                        if (i & 1) == 0 {
  333.                            x = x & LOWER_MASK;
  334.                        } else {
  335.                            x = x >> 64;
  336.                        }
  337.                        let mut y = ord.1[j >> 1];
  338.                        if (j & 1) == 0 {
  339.                            y = y & LOWER_MASK;
  340.                        } else {
  341.                            y = y >> 64;
  342.                        }
  343.                        let dest = len + i + j;
  344.                        let mut res = ret[dest].overflowing_add(x * y);
  345.                        ret[dest] = res.0;
  346.                        let mut next = dest + 1;
  347.                        while res.1 {
  348.                            ret[next] += 1;
  349.                            if ret[next] != 0 {
  350.                                res.1 = false
  351.                            }
  352.                            next += 1
  353.                        }
  354.                    }
  355.                }
  356.                let mut carry = 0;
  357.                let mut final_len = 0;
  358.                for i in 0..len {
  359.                    let mut new_carry = 0;
  360.                    let dest = len + 2 * i;
  361.                    let res = ret[dest].overflowing_add(carry);
  362.                    ret[i] = res.0;
  363.                    if res.1 {
  364.                        new_carry += 1;
  365.                    }
  366.                    let res = ret[i].overflowing_add((ret[dest + 1] & LOWER_MASK) << 64);
  367.                    ret[i] = res.0;
  368.                    if ret[i] != 0 {
  369.                        final_len = i + 1;
  370.                    }
  371.                    if res.1 {
  372.                        new_carry += 1;
  373.                    }
  374.                    carry = new_carry + ret[dest + 1] >> 64;
  375.                }
  376.                ret.resize(final_len, 0);
  377.                debug_assert!(ret.len() == 1 || ret[ret.len() - 1] != 0);
  378.                BigUInt {
  379.                    val: ret,
  380.                }
  381.            }
  382.        }
  383.    };
  384. }
  385.  
  386.  
  387. macro_rules! implBigUIntDiv {
  388.    ($lhsType:ty, $rhsType:ty, $($lhsRefs:ident)*, $($rhsRefs:ident)*, $($generics:tt)*) => {
  389.        impl$($generics)* ops::Div<$rhsType> for $lhsType {
  390.            type Output = BigUInt;
  391.            
  392.            fn div(self, rhs: $rhsType) -> BigUInt {
  393.                let mut pows : Vec<BigUInt> = Vec::new();
  394.                pows.push(toVal!(&rhs, $($rhsRefs)*).clone());
  395.                let mut pow_len = 1;
  396.                while &pows[pow_len - 1] < toVal!(&self, $($lhsRefs)*) {
  397.                    let next_sq = &pows[pow_len - 1] + &pows[pow_len - 1];
  398.                    pows.push(next_sq);
  399.                    pow_len += 1;
  400.                }
  401.                let mut div : Vec<u128> = Vec::new();
  402.                let mut div_len = self.val.len();
  403.                div.resize(div_len, 0);
  404.                let mut ret = toVal!(&self, $($lhsRefs)*).clone();
  405.                while ret >= pows[0] {
  406.                    while pows[pow_len - 1] > ret {
  407.                        pow_len -= 1;
  408.                    }
  409.                    let mut bucket = (pow_len - 1) / 128;
  410.                    let res = div[bucket].overflowing_add(1 << ((pow_len - 1) % 128));
  411.                    div[bucket] = res.0;
  412.                    if res.1 {
  413.                        loop {
  414.                            bucket += 1;
  415.                            if !div[bucket] == 0 {
  416.                                div[bucket] = 0;
  417.                            } else {
  418.                                div[bucket] += 1;
  419.                                break;
  420.                            }
  421.                        }
  422.                    }
  423.                    ret = ret - &pows[pow_len - 1];
  424.                }
  425.                while div_len > 1 && div[div_len - 1] == 0 {
  426.                    div_len -= 1;
  427.                }
  428.                div.resize(div_len, 0);
  429.                BigUInt {
  430.                    val: div,
  431.                }
  432.            }
  433.        }
  434.    };
  435. }
  436.  
  437. macro_rules! implBigUIntRem {
  438.    ($lhsType:ty, $rhsType:ty, $($lhsRefs:ident)*, $($rhsRefs:ident)*, $($generics:tt)*) => {
  439.        impl$($generics)* ops::Rem<$rhsType> for $lhsType {
  440.            type Output = BigUInt;
  441.            
  442.            fn rem(self, rhs: $rhsType) -> BigUInt {
  443.                let mut pows : Vec<BigUInt> = Vec::new();
  444.                pows.push(toVal!(&rhs, $($rhsRefs)*).clone());
  445.                let mut pow_len = 1;
  446.                while &pows[pow_len - 1] < toVal!(&self, $($lhsRefs)*) {
  447.                    let next_sq = &pows[pow_len - 1] + &pows[pow_len - 1];
  448.                    pows.push(next_sq);
  449.                    pow_len += 1;
  450.                }
  451.                let mut ret = toVal!(&self, $($lhsRefs)*).clone();
  452.                while ret >= pows[0] {
  453.                    while pows[pow_len - 1] > ret {
  454.                        pow_len -= 1;
  455.                    }
  456.                    ret = ret - &pows[pow_len - 1];
  457.                }
  458.                ret
  459.            }
  460.        }
  461.    };
  462. }
  463.  
  464. macro_rules! implBigUIntTypes {
  465.    ($implMacro:ident) => {
  466.        $implMacro!(&'a BigUInt, &'b BigUInt, R, R, <'a, 'b>);
  467.        $implMacro!(&'a BigUInt, BigUInt, R, , <'a>);
  468.        $implMacro!(BigUInt, &'b BigUInt, , R, <'b>);
  469.        $implMacro!(BigUInt, BigUInt, , , <>);
  470.        
  471.        $implMacro!(&&'a BigUInt, &&'b BigUInt, R R, R R, <'a, 'b>);
  472.        $implMacro!(&&'a BigUInt, &BigUInt, R R, R, <'a>);
  473.        $implMacro!(&BigUInt, &&'b BigUInt, R, R R, <'b>);
  474.        $implMacro!(&&'a BigUInt, BigUInt, R R, , <'a>);
  475.        $implMacro!(BigUInt, &&'b BigUInt, , R R, <'b>);
  476.    }
  477. }
  478.  
  479. implBigUIntTypes!(implBigUIntAdd);
  480. implBigUIntTypes!(implBigUIntSub);
  481. implBigUIntTypes!(implBigUIntMul);
  482. implBigUIntTypes!(implBigUIntDiv);
  483. implBigUIntTypes!(implBigUIntRem);
  484. //implBigUInt!(Add, add, +);
  485. //implBigUInt!(Sub, sub, -);
  486. //implBigUInt!(Div, div, /);
  487.  
  488. macro_rules! bigeval {
  489.    // Ignore tokens that are member accesses
  490.    (@parsing ($($stack:tt)*) . $member:tt $($rest:tt)*) => {
  491.        {
  492.            bigeval!(@parsing ($($stack)* . $member) $($rest)*)
  493.        }
  494.    };
  495.    
  496.    // Power mod a ** b % c shortcut
  497.    // Ketwords with higher precedence: as - * ! & &mut
  498.    // None of them apply so it can be ignored
  499.    (@parsing ($($stack:tt)*) $lhs:tt * * $rhs:tt % $modulus:tt $($rest:tt)*) => {
  500.        {
  501.            bigeval!(@parsing ($($stack)* bigeval!($lhs).powmod(bigeval!($rhs), bigeval!($modulus))) $($rest)*)
  502.        }
  503.    };
  504.    
  505.    // Power function a ** b shortcut
  506.    (@parsing ($($stack:tt)*) $lhs:tt * * $rhs:tt $($rest:tt)*) => {
  507.        {
  508.            bigeval!(@parsing ($($stack)* bigeval!($lhs).pow(bigeval!($rhs))) $($rest)*)
  509.        }
  510.    };
  511.    
  512.    // Dereference identifiers
  513.    (@parsing ($($stack:tt)*) $id:ident $($rest:tt)*) => {
  514.        {
  515.            bigeval!(@parsing ($($stack)* & $id) $($rest)*)
  516.        }
  517.    };
  518.    
  519.    // Recurse on parenthesis
  520.    (@parsing ($($stack:tt)*) ($($inside:tt)+)) => {
  521.        {
  522.            //bigeval!(@parsing (  $($i)* (bigeval!($($k)*))  ))
  523.            $($stack)* (bigeval!($($inside)*))
  524.        }
  525.    };
  526.    
  527.    // Recurse on parenthesis, without injecting a phantom AST node
  528.    (@parsing ($($stack:tt)*) ()) => {
  529.        {
  530.            //bigeval!(@parsing (  $($i)* (bigeval!($($k)*))  ))
  531.            $($stack)* ()
  532.        }
  533.    };
  534.    
  535.    // Ignore remaining tokens
  536.    (@parsing ($($stack:tt)*) $token:tt $($rest:tt)*) => {
  537.        {
  538.            bigeval!(@parsing ($($stack)* $token) $($rest)*)
  539.        }
  540.    };
  541.    
  542.    // No more tokens to pop, so return the stack
  543.    (@parsing ($($stack:tt)*)) => {
  544.        {
  545.            $($stack)*
  546.        }
  547.    };
  548.    
  549.    // Initialize with an empty stack
  550.    ($($tokens:tt)*) => {
  551.        {
  552.            bigeval!(@parsing () $($tokens)*)
  553.        }
  554.    };
  555. }
  556.  
  557. struct P {
  558.    x : BigUInt,
  559. }
  560.  
  561. fn test() {
  562.    let a : BigUInt = 9.into();
  563.    let b : BigUInt = 3.into();
  564.    let c : BigUInt = 2.into();
  565.    //println!("Hello, world! {:?}", &a / &b);
  566.    let myp = P { x : 2.into() };
  567.    let v = vec![&a, &b, &c];
  568.    //trace_macros!(true);
  569.    let d = bigeval!(a + b * myp.x.sq() + a ** (&b) % c + a ** b - v[5 - 4] * c);
  570.    //d = &a + &b - &c;
  571.    //trace_macros!(false);
  572.    //println!("Hello, world! {:?}", d - BigUInt::new(3));
  573.    
  574.    let mut f = BigUInt::new(1);
  575.    for _ in 0..100 {
  576.        f = &f * BigUInt::new(5);
  577.    }
  578.    let mut g = BigUInt::new(1);
  579.    for i in 0..105 {
  580.        //println!("g = 5^{}: {}", i, g);
  581.        //println!("f: {}", f);
  582.        //println!("g % f = {}", &g % &f);
  583.        g = &g * BigUInt::new(5);
  584.    }
  585.    //println!("5^100: {}", BigUInt::new(5).pow(&BigUInt::new(100)));
  586.    //println!("5^100 % 10000000: {}", BigUInt::new(5).powmod(&BigUInt::new(100), &BigUInt::new(10000000)));
  587.    /*for i in 0..105 {
  588.        println!("g = 5^{}: {}", 105 - i, g);
  589.        println!("f: {}", f);
  590.        println!("g % f = {}", &g % &f);
  591.        g = &g / BigUInt::new(5);
  592.    }*/
  593.    let k = a.clone();
  594.    //println!("Hello, world! {}", &a + k);
  595.    //println!("ToHex: {}", BigUInt::parse_hex("AB84E91F9D89F9AB84E91F9D89F9AB84E91F9D89F9AB84E91F9D89F9".to_string()));
  596. }
  597.  
  598. #[derive(PartialEq, Clone, Debug)]
  599. struct Point {
  600.    x: BigUInt,
  601.    y: BigUInt
  602. }
  603.  
  604. fn point_add(p: &Point, q: &Point) -> Point {
  605.    println!("p: {:?}", p);
  606.    println!("q: {:?}", q);
  607.    let P: BigUInt = BigUInt::parse_hex("115792089237316195423570985008687907853269984665640564039457584007908834671663".to_string());
  608.  
  609.    let lam: BigUInt = if p == q {
  610.        BigUInt::new(3) * &p.x * &p.x * ((BigUInt::new(2) * &p.y) % &P).powmod(&(&P - BigUInt::new(2)), &P)
  611.    } else {
  612.        &(&q.x - &p.x).powmod(&(&P - BigUInt::new(2)), &P) * (&q.y - &p.y) % &P
  613.    };
  614.    let rx = lam.clone().pow(&BigUInt::new(2)) - &p.x - &q.x;
  615.    let ry: BigUInt = lam * (&p.x - &rx) - &p.y;
  616.  
  617.    let ret = Point{x: rx % &P, y: ry % &P};
  618.    println!("ret: {:?}", ret);
  619.    ret
  620. }
  621.  
  622. fn point_mul(p: &Point, d: u32) -> Point {
  623.    let mut n: Point = (*p).clone();
  624.    let mut q: Option<Point> = None;
  625.  
  626.    let binary: String = format!("{:0256b}", d);
  627.    for (i, digit) in binary.chars().rev().enumerate() {
  628.        if digit == '1' {
  629.            q = match q { None => Some(n.clone()), Some(i) => Some(point_add(&i, &n)) }
  630.        }
  631.        n = point_add(&n, &n);
  632.    }
  633.    q.unwrap()
  634. }
  635.  
  636. fn main() {
  637.    //test();
  638.    
  639.    let G: Point = Point {
  640.        x: BigUInt::parse_hex("79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798".to_string()),
  641.        y: BigUInt::parse_hex("483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8".to_string())
  642.    };
  643.  
  644.    let res = point_mul(&G, 5);
  645.    println!(" {}", res.x);
  646.    println!(" {}", res.y);
  647. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!