25 people like it.
Like the snippet!
Project Euler #182
The RSA encryption is based on the following procedure:
Generate two distinct primes p and q. Compute n=pq and phi=(p1)(q1).
Find an integer e, 1
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:

///Simple gcd with ifs
///Nice moment: all recs there transform to whiles.
let rec gcd a b =
if b = 0L then a
else gcd b (a % b)
(Simple gcd with match)
///Binary gcd with match
let rec gcdBin a b =
match a, b with
0L, _ _, 0L > a  b
_ when (a &&& 1L)  (b &&& 1L) = 0L >
gcdBin (a >>> 1) (b >>> 1) <<< 1
_ when a &&& 1L = 0L >
gcdBin (a >>> 1) b
_ when b &&& 1L = 0L >
gcdBin a (b >>> 1)
_ when a > b >
gcdBin ((a  b) >>> 1) b
_ >
gcdBin ((b  a) >>> 1) a
(Binary gcd with ifs)
(* The minimum number of unconcealed messages is
(1 + gcd (e1) (q1)) * (1 + gcd (e1) (p1)) = 9
So the gcds there should be equal to 2 *)
let sum p q =
let phi = (p  1L) * (q  1L) in
[3L..2L..phi  1L]
//Realization using filter is maybe more beautiful, but less efficient
> List.sumBy (fun e >
if gcd e phi = 1L &&
gcd (e  1L) (q  1L) = 2L &&
gcd (e  1L) (p  1L) = 2L
then e
else 0L)
printfn "%A" < sum 1009L 3643L //399788195976L
(* The gcd test for 10000 random values says 'Be simple!':
simple gcd + if: 00.0058234
binary gcd + if: 00.0066124
binary gcd + match: 00.0067200
simple gcd + match: 00.0067880
*)

val gcd : a:int64 > b:int64 > int64
Full name: Script.gcd
Simple gcd with ifs
Nice moment: all recs there transform to whiles.
val a : int64
val b : int64
let rec gcd' a b =
match b with
0L > a
_ > gcd' b (a % b)
val gcdBin : a:int64 > b:int64 > int64
Full name: Script.gcdBin
Binary gcd with match
let rec gcdBin' a b =
if a = 0L  b = 0L then a  b
else if (a &&& 1L)  (b &&& 1L) = 0L then
gcdBin' (a >>> 1) (b >>> 1) <<< 1
else if a &&& 1L = 0L then gcdBin' (a >>> 1) b
else if b &&& 1L = 0L then gcdBin' a (b >>> 1)
else if a > b then gcdBin' ((a  b) >>> 1) b
else gcdBin' ((b  a) >>> 1) a
val sum : p:int64 > q:int64 > int64
Full name: Script.sum
val p : int64
val q : int64
val phi : int64
Multiple items
module List
from Microsoft.FSharp.Collections

type List<'T> =
 ( [] )
 ( :: ) of Head: 'T * Tail: 'T list
interface IEnumerable
interface IEnumerable<'T>
member Head : 'T
member IsEmpty : bool
member Item : index:int > 'T with get
member Length : int
member Tail : 'T list
static member Cons : head:'T * tail:'T list > 'T list
static member Empty : 'T list
Full name: Microsoft.FSharp.Collections.List<_>
val sumBy : projection:('T > 'U) > list:'T list > 'U (requires member ( + ) and member get_Zero)
Full name: Microsoft.FSharp.Collections.List.sumBy
val e : int64
val printfn : format:Printf.TextWriterFormat<'T> > 'T
Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.printfn
More information