Changeset 0bd2cb in git
 Timestamp:
 Apr 22, 2015, 5:38:23 PM (8 years ago)
 Branches:
 (u'spielwiese', '8e0ad00ce244dfd0756200662572aef8402f13d5')
 Children:
 8d36901c8c5e1e21217bfb861bc77db74a876182
 Parents:
 9fce789c50beb6e5e309f48b6b7f2ce7e57597ae
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

Singular/LIB/crypto.lib
r9fce78 r0bd2cb 4 4 info=" 5 5 LIBRARY: crypto.lib Procedures for teaching cryptography 6 AUTHOR: Gerhard Pfister, pfister@mathematik.unikl.de 6 AUTHORS: Gerhard Pfister, pfister@mathematik.unikl.de 7 @* David Brittinger, dativ@gmx.net 7 8 8 9 OVERVIEW: … … 48 49 factorLenstraECM(N,S,B,[]) Lenstra's factorization 49 50 ECPP(N) primalytest of GoldwasserKilian 51 calculate_ordering(num1, primitive, mod1) Calculates x so that primitive^x == num1 mod mod1 52 is_primitive_root(primitive, mod1) Checks if primitive is a primitive root modulo mod1 53 find_first_primitive_root(mod1) Returns the first primitive root modulo mod1, starting with 1 54 binary_add(binary_list) Adds a 1 to a binary encoded list 55 inverse_modulus(num,mod1) Finds a t so that t*num = 1 mod mod1 56 is_prime(n) Checks if n is prime 57 proc find_biggest_index(a) Returns the index of the biggest element of a 58 find_index(a,e) Returns the list index of element e in list a. Returns 0 if e is not in a 59 subset_sum01(list knapsack, int solution) solves the subsetsumknapsackproblem by calculating all subsets and choosing the right solution 60 subset_sum02(list knapsack, int sol) solves the subsetsumknapsackproblem with a naive greedy algorithm 61 unbounded_knapsack(list knapsack, list profit, int capacity) solves the unbounded_knapsackproblem, needing a list of knapsack weights, a list of profits and a capacity 62 multidimensional_knapsack(matrix m, list capacities, list profits) solves the multidimensional_knapsackproblem by using the PECH algorithm, needing a weight matrix m, a list of capacities and a list of profits 63 naccache_stern_generation(int key, int primenum) generates a hard knapsack for the NaccacheStern Kryptosystem for given key and prime modulus 64 naccache_stern_encryption(list knapsack, list message, int primenum) encrypts a message with the NaccacheStern Kryptosystem, using a hard knapsack, a message encoded as binary list and a prime modulus 65 naccache_stern_decryption(list knapsack, int key, int primenum, int message) decrypts a message with the NaccacheStern Kryptosystem, using the easy knapsack, the key, the prime modulus and the message encoded as integer 66 m_merkle_hellman_transformation(list knapsack, int primitive, int mod1) generates a hard knapsack for the multiplicative MerkleHellman Kryptosystem for a given easy knapsack and a primitive root for a modulus mod1 67 m_merkle_hellman_encryption(list knapsack, list message) encrypts a message with the multiplicative MerkleHellman Kryptosystem, using a hard knapsack and a message encoded as binary list 68 m_merkle_hellman_decryption(list knapsack, bigint primitive, bigint mod1, int message) decrypts a message with the multiplicative MerkleHellman Kryptosystem, using the easy knapsack, the key given by the primitive root, the modulus mod1 and the message encoded as integer 69 merkle_hellman_transformation(list knapsack, int key, int mod1 generates a hard knapsack for the MerkleHellman Kryptosystem for a given easy knapsack , a multiplicator key and a modulus mod1 70 merkle_hellman_encryption(list knapsack, list message) encrypts a message with the MerkleHellman Kryptosystem, using a hard knapsack and a message encoded as binary list 71 merkle_hellman_decryption(list knapsack, int key, int mod1, int message) decrypts a message with the multiplicative MerkleHellman Kryptosystem, using the hard knapsack, the key, the modulus mod1 and the message encoded as integer 72 super_increasing_knapsack(int ksize) Creates the smallest superincreasing knapsack of given size ksize 73 h_increasing_knapsack(int ksize, int h) Creates the smallest hincreasing knapsack of given size ksize and h 74 injective_knapsack(int ksize, int kmaxelement) Creates all list of all injective knapsacks of given size ksize and maximal element kmaxelement 75 calculate_max_sum(list a) Calculates the maximal sum of a given knapsack a 76 is_injective(list a) Checks if knapsack a is injective 77 is_h_injective(list a, int h) Checks if knapsack a is hinjective 78 is_fix_injective(list a) Checks if knapsack a is fixinjective 79 three_elements(list out, int iterations) Creates the smallest injective knapsack with a given injective_knapsack by using the threeelementsalgorithm with a given number of iterations 50 80 51 81 [parameters in square brackets are optional] … … 53 83 54 84 LIB "poly.lib"; 85 LIB "atkins.lib"; 55 86 56 87 /////////////////////////////////////////////////////////////////////////////// … … 2070 2101 t; 2071 2102 } 2072 2103 /* 2104 * set stuff 2105 * */ 2106 static proc set_multiply_list_content(list h) 2107 "USAGE: set_multiply_list_content(h) 2108 RETURN: An integer c als product of all elements in h 2109 EXAMPLE: example set_multiply_list_content; shows an example; 2110 " 2111 { 2112 int c = 1; 2113 for (int i=1;i<=size(h);i++) 2114 { 2115 c = c*h[i]; 2116 } 2117 return(c); 2118 } 2119 example 2120 { 2121 "EXAMPLE:"; echo = 2; 2122 list h=2,4,5; 2123 set_multiply_list_content(h); 2124 } 2125 2126 static proc set_delete_certain_element(list a, int e) 2127 "USAGE: set_delete_certain_element(a,e) 2128 RETURN: A list a without element e. If e was not in the list before, a will not be changed 2129 EXAMPLE: example set_delete_certain_element; shows an example. 2130 " 2131 { 2132 list output_list = a; 2133 for (int i=1;i<=size(a);i++) 2134 { 2135 if (a[i]==e) 2136 { 2137 output_list = delete(output_list,i); 2138 } 2139 } 2140 return(output_list); 2141 } 2142 example 2143 { 2144 "EXAMPLE:"; echo = 2; 2145 list h=2,4,5; 2146 set_delete_certain_element(h,4); 2147 set_delete_certain_element(h,10); 2148 } 2149 2150 static proc set_bubblesort_int(list output_list) 2151 "USAGE: set_bubblesort_int(output_list) 2152 RETURN: An ascending sorted list with integer values. 2153 EXAMPLE: set_bubblesort_int; shows an example. 2154 " 2155 { 2156 output_list = bubblesort(output_list); 2157 //Cast every value into an integer 2158 for (int i=1; i<=size(output_list);i++) 2159 { 2160 output_list[i] = int(output_list[i]); 2161 } 2162 return(output_list); 2163 } 2164 example 2165 { 2166 "EXAMPLE:"; echo = 2; 2167 list output_list=10,4,5,24,9; 2168 set_bubblesort_int(output_list); 2169 } 2170 2171 static proc set_is_set(list a) 2172 "USAGE: set_is_set(a) 2173 RETURN: 1 if the list is a set, 0 the list contains any duplicated elements 2174 EXAMPLE: set_is_set; shows an example. 2175 " 2176 { 2177 int i,v; 2178 for (v=1; v<=size(a); v++) 2179 { 2180 for (i=v+1; i<=size(a); i++) 2181 { 2182 if (a[i]==a[v]) 2183 { 2184 return(0); 2185 } 2186 } 2187 } 2188 return(1); 2189 } 2190 example 2191 { 2192 "EXAMPLE:"; echo = 2; 2193 list set = 1,5,10,2; 2194 list noset = 1,5,10,2,5; 2195 set_is_set(set); 2196 set_is_set(noset); 2197 } 2198 2199 static proc set_contains(list a, int e) 2200 "USAGE: set_contains(a,e) 2201 RETURN: 1 if the list contains e, 0 otherwise 2202 EXAMPLE: set_contains; shows an example. 2203 " 2204 { 2205 for (int v=1; v<=size(a); v++) 2206 { 2207 if (a[v]==e) 2208 { 2209 return(1); 2210 } 2211 } 2212 return(0); 2213 } 2214 example 2215 { 2216 "EXAMPLE:"; echo = 2; 2217 list set = 1,5,10,2; 2218 set_contains(set,5); 2219 set_contains(set,40); 2220 } 2221 2222 static proc set_delete_duplicates(list a) 2223 "USAGE: set_delete_duplicates(a) 2224 RETURN: a list a without any duplicated elements 2225 EXAMPLE: set_delete_duplicates; shows an example. 2226 " 2227 { 2228 int i; 2229 list output_list = a[1]; 2230 for (i=1; i<=size(a); i++) 2231 { 2232 if (set_contains(output_list,a[i])==0) 2233 { 2234 output_list = insert(output_list,a[i]); 2235 } 2236 } 2237 return(output_list); 2238 } 2239 example 2240 { 2241 "EXAMPLE:"; echo = 2; 2242 list set = 1,5,10,2,10,5; 2243 set_delete_duplicates(set); 2244 } 2245 2246 static proc set_equals(list a,list b) 2247 "USAGE: set_equals(a, b) 2248 RETURN: 1 if the lists are equal from a setstructure standpoint, 0 otherwise 2249 EXAMPLE: set_equals; shows an example. 2250 " 2251 { 2252 //Checks if the lists have the same length 2253 if (size(a)!=size(b)) 2254 { 2255 return(0); 2256 } 2257 2258 //Sorts the lists 2259 a = set_bubblesort_int(a); 2260 b = set_bubblesort_int(b); 2261 2262 //Checks every single element of both lists 2263 for (int i=1; i<=size(a); i++) 2264 { 2265 if (a[i]!=b[i]) 2266 { 2267 return(0); 2268 } 2269 } 2270 return(1); 2271 } 2272 example 2273 { 2274 "EXAMPLE:"; echo = 2; 2275 list set1 = 1,5,10,2; 2276 list set2 = 10,2,5,1; 2277 list set3 = 1,5,9,2; 2278 set_equals(set1,set2); 2279 set_equals(set1,set3); 2280 } 2281 2282 static proc set_insert(list a, int e) 2283 "USAGE: set_insert(a,e) 2284 RETURN: list a containing element e 2285 EXAMPLE: set_insert; shows an example. 2286 " 2287 { 2288 if(set_contains(a,e)) 2289 { 2290 return(a); 2291 } 2292 else 2293 { 2294 a=insert(a,e); 2295 return(a); 2296 } 2297 } 2298 example 2299 { 2300 "EXAMPLE:"; echo = 2; 2301 list set = 1,5,10,2; 2302 set_insert(set,5); 2303 set_insert(set,22); 2304 } 2305 2306 static proc set_union(list a, list b) 2307 "USAGE: set_union(a, b) 2308 RETURN: list a as union of a and b 2309 EXAMPLE: set_union; shows an example. 2310 " 2311 { 2312 for (int i=1; i<=size(b); i++) 2313 { 2314 if (set_contains(a,b[i])==0) 2315 { 2316 a = insert(a,b[i]); 2317 } 2318 } 2319 return(a); 2320 } 2321 example 2322 { 2323 "EXAMPLE:"; echo = 2; 2324 list set1 = 1,5,10,2; 2325 list set2 = 5,10,93,58,29; 2326 set_union(set1,set2); 2327 } 2328 2329 static proc set_section(list a, list b) 2330 "USAGE: set_section(a, b) 2331 RETURN: list output_list as intersection of a and b 2332 EXAMPLE: set_section; shows an example. 2333 " 2334 { 2335 list output_list; 2336 for (int i=1; i<=size(a); i++) 2337 { 2338 if (set_contains(b,a[i])==1) 2339 { 2340 output_list = insert(output_list,a[i]); 2341 } 2342 } 2343 return(output_list); 2344 } 2345 example 2346 { 2347 "EXAMPLE:"; echo = 2; 2348 list set1 = 1,5,10,2; 2349 list set2 = 5,10,93,58,29; 2350 set_section(set1,set2); 2351 } 2352 2353 static proc set_list_delete_duplicates(list a) 2354 "USAGE: set_list_delete_duplicates(a) 2355 RETURN: list output_list with no duplicated lists 2356 EXAMPLE: set_list_delete_duplicates; shows an example. 2357 " 2358 { 2359 int v; 2360 int i; 2361 int counter; 2362 int out_size; 2363 list output_list=insert(output_list,a[1]); 2364 //Create a new list and try to insert every list element from a into that list. If a list is already inserted into the 2365 //new list, do nothing. 2366 for (i=2; i<=size(a); i++) 2367 { 2368 out_size = size(output_list); 2369 counter = 0; 2370 2371 for (v=1; v<=out_size; v++) 2372 { 2373 if (set_equals(output_list[v],a[i])==1) 2374 { 2375 counter++; 2376 } 2377 } 2378 if (counter==0) 2379 { 2380 output_list = insert(output_list,a[i]); 2381 } 2382 } 2383 return(output_list); 2384 } 2385 example 2386 { 2387 "EXAMPLE:"; echo = 2; 2388 list set1 = 1,5,10,2; 2389 list set2 = 1,10,2,5; 2390 list set3 = 1,2,3; 2391 list superset = set1,set2,set3; 2392 set_list_delete_duplicates(superset); 2393 } 2394 2395 static proc set_construct_increasing_set(int maxelement) 2396 "USAGE: set_construct_increasing_set(maxelement) 2397 RETURN: list output_list with increasing elements from 1 to maxelement 2398 EXAMPLE: set_construct_increasing_set; shows an example. 2399 " 2400 { 2401 list output_list; 2402 for (int i=1; i<=maxelement; i++) 2403 { 2404 output_list = insert(output_list, i); 2405 } 2406 return(output_list); 2407 } 2408 example 2409 { 2410 "EXAMPLE:"; echo = 2; 2411 set_construct_increasing_set(10); 2412 } 2413 2414 static proc set_addtoall(list a, int element) 2415 "USAGE: set_addtoall(a,alement) 2416 RETURN: Transformed list with e_i+element for every element e_i in list a 2417 EXAMPLE: set_addtoall; shows an example. 2418 " 2419 { 2420 list output_list; 2421 int c; 2422 for (int i=1; i<=size(a); i++) 2423 { 2424 c = a[i]+element; 2425 output_list = insert(output_list,c); 2426 } 2427 return(set_turn(output_list)); 2428 } 2429 example 2430 { 2431 "EXAMPLE:"; echo = 2; 2432 list set = 1,5,10,2; 2433 set_addtoall(set,5); 2434 } 2435 2436 static proc set_turn(list a) 2437 "USAGE: set_turn(a) 2438 RETURN: Turned list a 2439 EXAMPLE: set_turn; shows an example. 2440 " 2441 { 2442 list output_list; 2443 for (int i=1; i<=size(a); i++) 2444 { 2445 output_list[size(a)+1i] = a[i]; 2446 } 2447 return(output_list); 2448 } 2449 example 2450 { 2451 "EXAMPLE:"; echo = 2; 2452 list set = 1,5,10; 2453 set_turn(set); 2454 } 2455 2456 static proc set_subset_set(list a) 2457 "USAGE: set_subset_set(a) 2458 RETURN: Set of subsets 2459 EXAMPLE: set_subset_set; shows an example. 2460 " 2461 { 2462 int v; 2463 int choice; 2464 list output_list; 2465 list start = a[1]; 2466 list insertion_list; 2467 int output_length; 2468 output_list = insert(output_list,start); 2469 2470 for (int i=2; i<=size(a); i++) 2471 { 2472 choice = 0; 2473 start = a[i]; 2474 output_list = insert(output_list,start); 2475 output_length = size(output_list); 2476 for (v=2; v<=output_length; v++) 2477 { 2478 insertion_list = set_insert(output_list[v],a[i]); 2479 output_list = insert(output_list, insertion_list,size(output_list)); 2480 } 2481 } 2482 return(output_list); 2483 } 2484 example 2485 { 2486 "EXAMPLE:"; echo = 2; 2487 list set = 1,5,10; 2488 set_subset_set(set); 2489 } 2490 /*  2491 * knapsack_utilities: Utility functions needed for knapsack 2492 * */ 2493 proc calculate_ordering(bigint num1, bigint primitive, bigint mod1) 2494 "USAGE: calculate_ordering(num1, primitive, mod1) 2495 RETURN: x so that primitive^x == num1 mod mod1 2496 EXAMPLE: example calculate_ordering; shows an example; 2497 " 2498 { 2499 for (int i=1;i<=int((mod12));i++) 2500 { 2501 if ((primitive^i%mod1)==num1) 2502 { 2503 return(i); 2504 } 2505 } 2506 return(0); 2507 } 2508 example 2509 { 2510 "EXAMPLE:"; echo = 2; 2511 bigint mod1 = 33; 2512 bigint primitive = 14; 2513 bigint num1 = 5; 2514 calculate_ordering(num1,primitive,mod1); 2515 } 2516 2517 proc is_primitive_root(bigint primitive, bigint mod1) 2518 "USAGE: is_primitive_root(primitive, mod1) 2519 RETURN: 1 if primitive is a primitive root modulo mod1, 0 otherwise 2520 EXAMPLE: example is_primitive_root; shows an example; 2521 " 2522 { 2523 list output_list; 2524 for (int i=1;i<=int((mod11));i++) 2525 { 2526 output_list = set_insert(output_list,int((primitive^i%mod1))); 2527 } 2528 if (bigint(size(output_list))==bigint(mod11)) 2529 { 2530 return(1); 2531 } 2532 else 2533 { 2534 return(0); 2535 } 2536 } 2537 example 2538 { 2539 "EXAMPLE:"; echo = 2; 2540 is_primitive_root(3,7); 2541 is_primitive_root(2,7); 2542 } 2543 2544 proc find_first_primitive_root(bigint mod1) 2545 "USAGE: find_first_primitive_root(mod1) 2546 RETURN: First primitive root modulo mod1, 0 if no root can be found. 2547 EXAMPLE: example find_first_primitive_root; shows an example; 2548 " 2549 { 2550 for (int i=0;i<=int(mod11);i++) 2551 { 2552 if (is_primitive_root(bigint(i),mod1)==1) 2553 { 2554 return(i); 2555 } 2556 } 2557 return(0); 2558 } 2559 example 2560 { 2561 "EXAMPLE:"; echo = 2; 2562 ring r = 0,x,lp; 2563 find_first_primitive_root(7); 2564 find_first_primitive_root(557); 2565 } 2566 2567 proc binary_add(list binary_list) 2568 "USAGE: binary_add(binary_list) 2569 RETURN: binary encoded list, increased by 1 2570 EXAMPLE: example binary_add; shows an example; 2571 " 2572 { 2573 int residual=1; 2574 int position = size(binary_list); 2575 while((residual==1)&&(position!=0)) 2576 { 2577 if(binary_list[position]==0) 2578 { 2579 binary_list[position]=1; 2580 residual=0; 2581 } 2582 else 2583 { 2584 binary_list[position]=0; 2585 position; 2586 } 2587 } 2588 if (position==0) 2589 { 2590 binary_list = insert(binary_list,1); 2591 } 2592 return(binary_list); 2593 } 2594 example 2595 { 2596 "EXAMPLE:"; echo = 2; 2597 ring r = 0,x,lp; 2598 list binary_list = 1,0,1,1,1; 2599 binary_add(binary_list); 2600 } 2601 2602 proc inverse_modulus(int num, int mod1) 2603 "USAGE: inverse_modulus(num, mod1) 2604 RETURN: inverse element of num modulo mod1 2605 EXAMPLE: example inverse_modulus; shows an example; 2606 " 2607 { 2608 if (num>=mod1) 2609 { 2610 return(0); 2611 } 2612 else 2613 { 2614 for (int i=1;i<mod1;i++) 2615 { 2616 if ((i*num%mod1)==1) 2617 { 2618 return(i); 2619 } 2620 } 2621 } 2622 } 2623 example 2624 { 2625 "EXAMPLE:"; echo = 2; 2626 ring r = 0,x,lp; 2627 int mod1 = 13; 2628 int num = 5; 2629 inverse_modulus(num,mod1); 2630 } 2631 2632 proc is_prime(int n) 2633 "USAGE: is_prime(n) 2634 RETURN: 1 if n is prime, 0 otherwise 2635 EXAMPLE: example is_prime; shows an example; 2636 " 2637 { 2638 int prime1 = 1; 2639 for (int i=n1;i>1;i) 2640 { 2641 if(n%i==0) 2642 { 2643 prime1 = 0; 2644 } 2645 } 2646 return(prime1); 2647 } 2648 example 2649 { 2650 "EXAMPLE:"; echo = 2; 2651 ring r = 0,x,lp; 2652 is_prime(10); 2653 is_prime(7); 2654 } 2655 2656 proc find_biggest_index(list a) 2657 "USAGE: find_biggest_index( a) 2658 RETURN: Returns the index of the biggest element of a 2659 EXAMPLE: example find_biggest_index; shows an example; 2660 " 2661 { 2662 list sortedlist = bubblesort(a); 2663 return(find_index(a,sortedlist[1])); 2664 } 2665 2666 proc find_index(list a, bigint e) 2667 "USAGE: find_index(a, e) 2668 RETURN: Returns the list index of element e in list a. Returns 0 if e is not in a 2669 EXAMPLE: example find_index; shows an example; 2670 " 2671 { 2672 for(int i=1;i<=size(a);i++) 2673 { 2674 if (bigint(a[i])==e) 2675 { 2676 return(i); 2677 } 2678 } 2679 return(0); 2680 } 2681 example 2682 { 2683 "EXAMPLE:"; echo = 2; 2684 list a = 1,5,20,6,37; 2685 find_index(a,20); 2686 find_index(a,6); 2687 find_index(a,100); 2688 } 2689 /*  2690 * Knapsack Algorithmus such as solving several knapsack problems, 2691 * kryptographic algorithms and algorithms for creatings suitable knapsacks 2692 *  */ 2693 proc subset_sum01(list knapsack, int solution) 2694 "USAGE: subset_sum01(knapsack,solution) 2695 RETURN: binary list of the positions of the elements included in the subset sum or 0 if no solution exists 2696 NOTE: This will return the first solution of the sskproblem, given be the smallest binary encoding. It wont return several solutions if they exist 2697 EXAMPLE: example subset_sum01; shows an example; 2698 " 2699 { 2700 int i; 2701 int v; 2702 int comparable; 2703 //Check if the knapsack is a set 2704 if (set_is_set(knapsack)==1) 2705 { 2706 //Create a binary list full of zeroes 2707 list binary_list; 2708 for (i=1;i<=size(knapsack);i++) 2709 { 2710 binary_list = insert(binary_list,0); 2711 } 2712 binary_list = binary_add(binary_list); 2713 2714 for(i=1;i<=2^(size(knapsack));i++) 2715 { 2716 comparable = 0; 2717 //Create the SubsetSum for the actual binary coding of binary_list 2718 for (v=1;v<=size(knapsack);v++) 2719 { 2720 comparable = comparable+knapsack[v]*binary_list[v]; 2721 } 2722 //Check if the sum equals the solution 2723 if (comparable==solution) 2724 { 2725 return(binary_list); 2726 } 2727 else 2728 { 2729 binary_list = binary_add(binary_list); 2730 } 2731 } 2732 return(0); 2733 } 2734 else 2735 { 2736 return(0); 2737 } 2738 } 2739 example 2740 { 2741 "EXAMPLE:"; echo = 2; 2742 list h=1,4,7,32; 2743 subset_sum01(h,20); 2744 subset_sum01(h,11); 2745 subset_sum01(h,33); 2746 } 2747 2748 proc subset_sum02(list knapsack, int sol) 2749 "USAGE: subset_sum02(knapsack,sol) 2750 RETURN: binary list of the positions of the elements included in the subset sum or 0 if no solution exists 2751 EXAMPLE: example subset_sum02; shows an example; 2752 " 2753 { 2754 list summands; 2755 int calcu; 2756 int i; 2757 //Create a sorted copy of the knapsack, calling it worksack 2758 list worksack = set_bubblesort_int(knapsack); 2759 int counter = 1; 2760 while((counter<=size(worksack))&&(sol>0)) 2761 { 2762 //Try to substract an element of the knapsack from the capacity. Create a list with all the summands used 2763 calcu = solworksack[counter]; 2764 if (calcu>=0) 2765 { 2766 sol = solworksack[counter]; 2767 summands = insert(summands,int(worksack[counter])); 2768 } 2769 counter++; 2770 } 2771 if(sol>0) 2772 { 2773 return(0); 2774 } 2775 2776 //Get the index of the summands of the original knapsack and change the bits in the binary list wich will be the solution 2777 list binary_list; 2778 for (i=1;i<=size(knapsack);i++) 2779 { 2780 binary_list = insert(binary_list,0); 2781 } 2782 2783 for (i=1; i<=size(knapsack);i++) 2784 { 2785 if (set_contains(summands,knapsack[i])==1) 2786 { 2787 binary_list[i]=1; 2788 } 2789 } 2790 return(binary_list); 2791 } 2792 example 2793 { 2794 "EXAMPLE:"; echo = 2; 2795 list h=1,4,7,32; 2796 subset_sum02(h,20); 2797 subset_sum02(h,11); 2798 subset_sum02(h,33); 2799 } 2800 2801 proc unbounded_knapsack(list knapsack, list profit, int capacity) 2802 "USAGE: unbounded_knapsack(knapsack,profit,capacity) 2803 RETURN: list of maximum profit of each iteration. For example, output_list[2] contains the maximum profit that can be achieved if the knapsack has capacity 2. 2804 EXAMPLE: unbounded_knapsack; shows an example; 2805 " 2806 { 2807 int i; 2808 int v; 2809 list output_list; 2810 for (i=1;i<=capacity+1;i++) 2811 { 2812 output_list = insert(output_list,0); 2813 } 2814 for (i=1;i<=capacity+1;i++) 2815 { 2816 for(v=1;v<=size(knapsack);v++) 2817 { 2818 if (knapsack[v]<i) 2819 { 2820 if(output_list[i]<(output_list[iknapsack[v]]+profit[v])) 2821 { 2822 output_list[i] = output_list[iknapsack[v]]+profit[v]; 2823 } 2824 } 2825 } 2826 } 2827 return(output_list); 2828 } 2829 example 2830 { 2831 "EXAMPLE:"; echo = 2; 2832 list h=1,4,7,32; 2833 list knapsack = 5,2; 2834 list profit = 10,3; 2835 int capacity = 5; 2836 unbounded_knapsack(knapsack,profit,capacity); 2837 } 2838 2839 proc multidimensional_knapsack(matrix m, list capacities, list profits) 2840 "USAGE: multidimensional_knapsack(m,capacities,profits) 2841 RETURN: binary list of the positions of the elements included in the optimal selection 2842 EXAMPLE: example multidimensional_knapsack; shows an example; 2843 " 2844 { 2845 int index; 2846 list output_list; 2847 list nolist; 2848 list y_list; 2849 list minmax_list; 2850 int i; 2851 int v; 2852 int checkint; 2853 //create the output_list full of zeroes with the length of all given selections 2854 for (i=1;i<=size(profits);i++) 2855 { 2856 output_list = insert(output_list,0); 2857 } 2858 2859 //Create the List E with all indices of the output_list that haven't been used yet. 2860 list E = set_turn(set_construct_increasing_set(size(profits))); 2861 2862 //Repeat till every index in E is used. 2863 while(size(E)>0) 2864 { 2865 y_list = nolist; 2866 for (i=1;i<=size(E);i++) 2867 { 2868 //Create all possible elements of y_i (y_list). minimax_list will be replaced of an empty list in each iteration 2869 minmax_list = nolist; 2870 for (v=1; v<=size(capacities);v++) 2871 { 2872 if (set_contains(E,v)==1) 2873 { 2874 minmax_list = insert(minmax_list, bigint(capacities[v])/bigint(m[v,E[i]])); 2875 } 2876 } 2877 //Sort the elements so that it is easy to pick the smallest one 2878 minmax_list = bubblesort(minmax_list); 2879 2880 //insert Element y_i into y_list, wich is the smallest of (b_i/w_ij) like in the PECH algorithm description. 2881 y_list = insert(y_list,minmax_list[size(minmax_list)],size(y_list)); 2882 2883 2884 } 2885 2886 //Check if all y_i in y_list are smaller than 1. If so, every additional selection will exceed the capacity and the algorithm stops. 2887 checkint=0; 2888 for(i=1;i<=size(y_list);i++) 2889 { 2890 if (y_list[i]>=1) 2891 { 2892 checkint=1; 2893 } 2894 } 2895 if (checkint==0) 2896 { 2897 return(output_list); 2898 } 2899 2900 2901 //Find the index of the selection and update the binary output_list 2902 minmax_list = nolist; 2903 for (i=1;i<=size(E);i++) 2904 { 2905 minmax_list = insert(minmax_list, profits[E[i]]*y_list[i],size(minmax_list)); 2906 } 2907 index = find_biggest_index(minmax_list); 2908 2909 output_list[E[index]]=1; 2910 2911 //Update the capacities by substracting the weights of the selection 2912 for (i=1;i<=size(capacities);i++) 2913 { 2914 capacities[i] = capacities[i] m[i,E[index]]; 2915 } 2916 E = set_delete_certain_element(E,index); 2917 2918 } 2919 return(output_list); 2920 } 2921 example 2922 { 2923 "EXAMPLE:"; echo = 2; 2924 ring r = 0,x,lp; 2925 matrix m[3][3] = 1,4,10,7,8,3,1,9,7; 2926 list c = 12,17,10; 2927 list p = 3,2,5; 2928 multidimensional_knapsack(m,c,p); 2929 } 2930 2931 proc naccache_stern_generation(int key, int primenum) 2932 "USAGE: naccache_stern_generation(key, primenum) 2933 RETURN: a hard knapsack list 2934 EXAMPLE: example naccache_stern_generation; shows an example; 2935 " 2936 { 2937 //Check if primenum is a prime and the gcdCondition holds 2938 if ((is_prime(primenum)==0)(gcd(key,(primenum1))!=1)) 2939 { 2940 return(0); 2941 } 2942 else 2943 { 2944 int i; 2945 int p; 2946 list primelist; 2947 int primecounter=2; 2948 //Generate the knapsack containing the smallest prime numbers so that primenum exceeds the product of all of them 2949 while(set_multiply_list_content(primelist)<primenum) 2950 { 2951 if (is_prime(primecounter)==1) 2952 { 2953 primelist = insert(primelist,primecounter); 2954 } 2955 primecounter++; 2956 } 2957 primelist = delete(primelist,1); 2958 2959 2960 //Generate the hard knapsack of the length of the prime numbers containing zeroes. 2961 list hardknapsack; 2962 for (i=1;i<=size(primelist);i++) 2963 { 2964 hardknapsack = insert(hardknapsack,0); 2965 } 2966 2967 //Create the elements of the hard knapsack 2968 primecounter = 1; 2969 bigint calcu; 2970 i=0; 2971 while (i<size(primelist)) 2972 { 2973 //Create some v_i^key%primenum and store it in calcu 2974 calcu = bigint(primecounter)^key%bigint(primenum); 2975 2976 //If calcu is one of the prime numbers in the knapsack, find the index and insert v_i in the hard knapsack at that given index 2977 if(set_contains(primelist,int(calcu))==1) 2978 { 2979 p=find_index(primelist,int(calcu)); 2980 hardknapsack[p] = primecounter; 2981 i++; 2982 } 2983 primecounter++; 2984 } 2985 return(hardknapsack); 2986 } 2987 } 2988 example 2989 { 2990 "EXAMPLE:"; echo = 2; 2991 naccache_stern_generation(5,292); 2992 naccache_stern_generation(5,293); 2993 } 2994 2995 proc naccache_stern_encryption(list knapsack, list message, int primenum) 2996 "USAGE: naccache_stern_encryption(knapsack, message, primenum) 2997 RETURN: an encrypted message as integer 2998 EXAMPLE: example naccache_stern_encryption; shows an example; 2999 " 3000 { 3001 bigint solution = 1; 3002 if (size(knapsack)==size(message)) 3003 { 3004 for(int i=1;i<=size(knapsack);i++) 3005 { 3006 solution = solution*((bigint(knapsack[i])^message[i])%bigint(primenum)); 3007 } 3008 return(solution); 3009 } 3010 else 3011 { 3012 return(0); 3013 } 3014 3015 } 3016 example 3017 { 3018 "EXAMPLE:"; echo = 2; 3019 //Please note that the values for primenum and hardknapsack have been obtained from the example of naccache_stern_generation! 3020 list hardknapsack = 85,164,117,44; 3021 int primenum = 293; 3022 list message = 1,0,1,0; 3023 naccache_stern_encryption(hardknapsack,message,primenum); 3024 } 3025 3026 proc naccache_stern_decryption(list knapsack, int key, int primenum, int message) 3027 "USAGE: naccache_stern_decryption(knapsack, key, primenum, message) 3028 RETURN: decrypted binary list 3029 EXAMPLE: example naccache_stern_decryption; shows an example; 3030 " 3031 { 3032 //create a binary list with the length of the knapsack containing zeros 3033 int k = int(bigint(message)^key%bigint(primenum)); 3034 int i; 3035 list binary_list; 3036 for (i=1;i<=size(knapsack);i++) 3037 { 3038 binary_list = insert(binary_list,0); 3039 } 3040 3041 //create primelist like in int naccache_stern_generation process 3042 list primelist; 3043 int primecounter=2; 3044 while(size(primelist)<size(knapsack)) 3045 { 3046 if (is_prime(primecounter)==1) 3047 { 3048 primelist = insert(primelist,primecounter); 3049 } 3050 primecounter++; 3051 } 3052 3053 //find divisors of k and update the binarylist in a way that the positions of the divisors in primelist are marked 3054 for (i=1;i<=size(primelist);i++) 3055 { 3056 if(k%primelist[i]==0) 3057 { 3058 binary_list[i]=1; 3059 } 3060 } 3061 return(binary_list); 3062 3063 } 3064 example 3065 { 3066 "EXAMPLE:"; echo = 2; 3067 //Please note that the values have been obtained from the example of naccache_stern_generation and naccache_stern_encryption! 3068 int primenum = 293; 3069 int message = 9945; 3070 int key = 5; 3071 list hardknapsack = 85,164,117,44; 3072 naccache_stern_decryption(hardknapsack,key,primenum,message); 3073 } 3074 3075 proc m_merkle_hellman_transformation(list knapsack, int primitive, int mod1) 3076 "USAGE: m_merkle_hellman_transformation(knapsack, primitive, mod1) 3077 RETURN: list containing a hard knapsack 3078 EXAMPLE: example m_merkle_hellman_transformation; shows an example; 3079 " 3080 { 3081 bigint new_element; 3082 list output_list; 3083 //calculate the primitiv root of every element in knapsack and insert it into a new knapsack 3084 for (int i=size(knapsack);i>=1;i) 3085 { 3086 new_element = calculate_ordering(knapsack[i],primitive,mod1); 3087 output_list = insert(output_list,int(new_element)); 3088 } 3089 return(output_list); 3090 } 3091 example 3092 { 3093 "EXAMPLE:"; echo = 2; 3094 //Please note that the values for primenum and hardknapsack have been obtained from the example of naccache_stern_generation and naccache_stern_encryption! 3095 list knapsack = 2,3,5,7; 3096 int mod1 = 211; 3097 int primitive = 2; 3098 m_merkle_hellman_transformation(knapsack,primitive,mod1); 3099 } 3100 3101 proc m_merkle_hellman_encryption(list knapsack, list message) 3102 "USAGE: m_merkle_hellman_encryption(knapsack, message) 3103 RETURN: an encrypted message as integer 3104 NOTE: This works in the same way as merkle_hellman_encryption. The additional function is created to keep consistency with the needed functions for every kryptosystem. 3105 EXAMPLE: example m_merkle_hellman_encryption; shows an example; 3106 " 3107 { 3108 return(merkle_hellman_encryption(knapsack,message)); 3109 } 3110 example 3111 { 3112 "EXAMPLE:"; echo = 2; 3113 //Please note that the values for primenum and hardknapsack have been obtained from the example of m_merkle_hellman_transformation! 3114 list knapsack = 1,43,132,139; 3115 list message = 1,0,0,1; 3116 m_merkle_hellman_encryption(knapsack,message); 3117 } 3118 3119 proc m_merkle_hellman_decryption(list knapsack, bigint primitive, bigint mod1, int message) 3120 "USAGE: m_merkle_hellman_decryption(knapsack, primitive, mod1, message) 3121 RETURN: decrypted binary list 3122 EXAMPLE: example merkle_hellman_decryption; shows an example; 3123 " 3124 { 3125 //Convert message 3126 int factorizing = int((primitive^message)%mod1); 3127 int i; 3128 3129 //Create binary list of length of the knapsack, containing zeroes. 3130 list binary_list; 3131 for (i=1;i<=size(knapsack);i++) 3132 { 3133 binary_list = insert(binary_list,0); 3134 } 3135 3136 //factorize the converted message, mark the factor positions in knapsack as bits in binary_list 3137 for (i=1;i<=size(knapsack);i++) 3138 { 3139 if(factorizing%knapsack[i]==0) 3140 { 3141 binary_list[i]=1; 3142 } 3143 } 3144 return(binary_list); 3145 } 3146 example 3147 { 3148 "EXAMPLE:"; echo = 2; 3149 //Please note that the values have been obtained from the example of m_merkle_hellman_encryption and m_merkle_hellman_transformation! 3150 list knapsack = 2,3,5,7; 3151 int message = 140; 3152 bigint primitive = 2; 3153 bigint mod1 = 211; 3154 m_merkle_hellman_decryption(knapsack,primitive,mod1,message); 3155 } 3156 3157 proc merkle_hellman_transformation(list knapsack, int key, int mod1) 3158 "USAGE: merkle_hellman_transformation(knapsack, key, mod1) 3159 RETURN: hard knapsack 3160 EXAMPLE: example merkle_hellman_transformation; shows an example; 3161 " 3162 { 3163 list output_list; 3164 int new_element; 3165 //transform every element in the knapsack with normal strong modular multiplication 3166 for (int i=size(knapsack);i>=1;i) 3167 { 3168 new_element=knapsack[i]*key%mod1; 3169 output_list = insert(output_list,new_element); 3170 } 3171 return(output_list); 3172 } 3173 example 3174 { 3175 "EXAMPLE:"; echo = 2; 3176 list knapsack = 1,3,5,12; 3177 int key = 3; 3178 int mod1 = 23; 3179 merkle_hellman_transformation(knapsack,key,mod1); 3180 } 3181 3182 proc merkle_hellman_encryption(list knapsack, list message) 3183 "USAGE: merkle_hellman_encryption(knapsack, message) 3184 RETURN: encrypted integer 3185 EXAMPLE: example merkle_hellman_encryption; shows an example; 3186 " 3187 { 3188 int solution = 0; 3189 if (size(knapsack)!=size(message)(set_is_set(knapsack)==0)) 3190 { 3191 return(0); 3192 } 3193 else 3194 { 3195 for (int i=1;i<=size(knapsack);i++) 3196 { 3197 solution = solution+knapsack[i]*message[i]; 3198 } 3199 return(solution); 3200 } 3201 } 3202 example 3203 { 3204 "EXAMPLE:"; echo = 2; 3205 //Please note that the values have been obtained from the example of merkle_hellman_transformation! 3206 list hardknapsack =3,9,15,13; 3207 list message = 0,1,0,1; 3208 merkle_hellman_encryption(hardknapsack,message); 3209 } 3210 3211 proc merkle_hellman_decryption(list knapsack, int key, int mod1, int message) 3212 "USAGE: merkle_hellman_decryption(knapsack, key, mod1, message) 3213 RETURN: decrypted binary list 3214 EXAMPLE: example merkle_hellman_decryption; shows an example; 3215 " 3216 { 3217 int new_element; 3218 int t = inverse_modulus(key,mod1); 3219 int transformed_message; 3220 list binary_list; 3221 if ((set_is_set(knapsack)==1)&&(key<mod1)) 3222 { 3223 //reconstruct easy knapsack be multiplying with the inverse modulus t 3224 list easy_knapsack; 3225 for (int i=size(knapsack);i>=1;i) 3226 { 3227 new_element=knapsack[i]*t%mod1; 3228 easy_knapsack = insert(easy_knapsack,new_element); 3229 } 3230 3231 //solve the easy knapsack problem with subset_sum01 or subset_sum02 3232 transformed_message = (message*t)%mod1; 3233 transformed_message; 3234 binary_list = subset_sum01(easy_knapsack,transformed_message); 3235 return(binary_list) 3236 } 3237 else 3238 { 3239 return(0) 3240 } 3241 } 3242 example 3243 { 3244 "EXAMPLE:"; echo = 2; 3245 //Please note that the values have been obtained from the example of merkle_hellman_decryption and merkle_hellman_transformation! 3246 list hardknapsack =3,9,15,13; 3247 int key = 3; 3248 int message = 22; 3249 int mod1 = 23; 3250 merkle_hellman_decryption(hardknapsack, key, mod1, message); 3251 } 3252 3253 proc super_increasing_knapsack(int ksize) 3254 "USAGE: super_increasing_knapsack(ksize) 3255 RETURN: superincreasing knapsack list 3256 EXAMPLE: super_increasing_knapsack; shows an example; 3257 " 3258 { 3259 list output_list = insert(output_list,1); 3260 int next_element; 3261 3262 for (int i=2; i<=ksize; i++) 3263 { 3264 next_element = calculate_max_sum(output_list)+1; 3265 output_list = insert(output_list,next_element); 3266 } 3267 return(output_list); 3268 } 3269 example 3270 { 3271 "EXAMPLE:"; echo = 2; 3272 super_increasing_knapsack(10); 3273 } 3274 3275 proc h_increasing_knapsack(int ksize, int h) 3276 "USAGE: h_increasing_knapsack(ksize, h) 3277 RETURN: hincreasing knapsack list 3278 EXAMPLE: h_increasing_knapsack; shows an example; 3279 " 3280 { 3281 int v; 3282 if (ksize<=h+1) 3283 { 3284 return(set_turn(super_increasing_knapsack(ksize))) 3285 } 3286 else 3287 { 3288 list out = set_turn(super_increasing_knapsack(h+1)); 3289 int next_element; 3290 for (int i=h+2; i<=ksize; i++) 3291 { 3292 next_element = 0; 3293 for (v=ih; v<=i1; v++) 3294 { 3295 next_element = next_element+out[v]; 3296 } 3297 next_element++; 3298 out = insert(out,next_element,size(out)); 3299 } 3300 return(out); 3301 } 3302 } 3303 example 3304 { 3305 "EXAMPLE:"; echo = 2; 3306 h_increasing_knapsack(10,5); 3307 } 3308 3309 proc injective_knapsack(int ksize, int kmaxelement) 3310 "USAGE: injective_knapsack(ksize, kmaxelement) 3311 RETURN: list of injective knapsacks with maximal element kmaxelement and size ksize 3312 EXAMPLE: injective_knapsack; shows an example; 3313 " 3314 { 3315 //Create a List of size ksize with the greatest possible elements keeping the set structure 3316 list list_of_lists; 3317 list A = insert(A,kmaxelement); 3318 int i; 3319 for (i=2;i<=ksize;i++) 3320 { 3321 A = insert(A,kmaxelement(i1)); 3322 } 3323 A = set_turn(A); 3324 list_of_lists = insert(list_of_lists,A); 3325 3326 //Create all possible sets containing the possible elements of A 3327 int residual; 3328 int position; 3329 while(A[1]==kmaxelement) 3330 { 3331 residual=3; 3332 position = ksize; 3333 while((residual!=0)) 3334 { 3335 if(A[position]==1) 3336 { 3337 A[position]=kmaxelementposition+1; 3338 residual=1; 3339 position; 3340 } 3341 else 3342 { 3343 A[position]=A[position]1; 3344 residual=0; 3345 } 3346 } 3347 //Insert the list into the overall list if its a set 3348 if (set_is_set(A)==1) 3349 { 3350 list_of_lists = insert(list_of_lists,A); 3351 } 3352 } 3353 //delete the first element since it is smaller than kmaxelement 3354 list_of_lists = delete(list_of_lists,1); 3355 //delete duplicates 3356 list_of_lists = set_list_delete_duplicates(list_of_lists); 3357 3358 //Check if the remaining knapsacks are injective 3359 list output_list; 3360 for(i=1;i<=size(list_of_lists);i++) 3361 { 3362 if (is_injective(list_of_lists[i])==1) 3363 { 3364 output_list=insert(output_list,list_of_lists[i]); 3365 } 3366 } 3367 return(output_list); 3368 } 3369 example 3370 { 3371 "EXAMPLE:"; echo = 2; 3372 injective_knapsack(3,9); 3373 } 3374 3375 proc calculate_max_sum(list a) 3376 "USAGE: calculate_max_sum(a) 3377 RETURN: sum of all elements in a 3378 EXAMPLE: calculate_max_sum; shows an example; 3379 " 3380 { 3381 int sum = a[1]; 3382 for (int i=2; i<=size(a);i++) 3383 { 3384 sum = sum+a[i]; 3385 } 3386 return(sum); 3387 } 3388 example 3389 { 3390 "EXAMPLE:"; echo = 2; 3391 list a = 1,5,3,2,12; 3392 calculate_max_sum(a); 3393 } 3394 3395 proc is_injective(list a) 3396 "USAGE: is_injective(a) 3397 RETURN: 1 if a is injective, 0 otherwise 3398 EXAMPLE: is_injective; shows an example; 3399 " 3400 { 3401 //Create all subsets of the set a 3402 list subsum = set_subset_set(a); 3403 list checklist=calculate_max_sum(subsum[1]); 3404 int calculator; 3405 for (int i=2; i<=size(subsum);i++) 3406 { 3407 //calculate the maximal subset_sum for every subset. Check if there are duplicated subset_sums. If so, a is not injective 3408 calculator = calculate_max_sum(subsum[i]); 3409 if (set_contains(checklist, calculator)) 3410 { 3411 return(0); 3412 } 3413 else 3414 { 3415 checklist = insert(checklist,calculator); 3416 } 3417 } 3418 return(1); 3419 } 3420 example 3421 { 3422 "EXAMPLE:"; echo = 2; 3423 list inj = 1,5,7,41; 3424 list non_inj = 1,2,3,4; 3425 is_injective(inj); 3426 is_injective(non_inj); 3427 } 3428 3429 proc is_h_injective(list a, int h) 3430 "USAGE: is_h_injective(a, h) 3431 RETURN: 1 if a is hinjective, 0 otherwise 3432 EXAMPLE: is_h_injective; shows an example; 3433 " 3434 { 3435 //Create all sets of subsets 3436 list subsetlist = set_subset_set(a); 3437 list h_subsetlist; 3438 //delete every list with elements more than h+1 since they are not needed to check hinjectivity 3439 for (int i=1; i<=size(subsetlist); i++) 3440 { 3441 if(size(subsetlist[i])<=h) 3442 { 3443 h_subsetlist = insert(h_subsetlist,subsetlist[i]); 3444 } 3445 } 3446 3447 //Check if the remaining max_sums do not occure more than once 3448 list checklist=calculate_max_sum(h_subsetlist[1]); 3449 int calculator; 3450 for (i=2; i<=size(h_subsetlist);i++) 3451 { 3452 calculator = calculate_max_sum(h_subsetlist[i]); 3453 if (set_contains(checklist, calculator)==1) 3454 { 3455 return(0); 3456 } 3457 else 3458 { 3459 checklist = insert(checklist,calculator); 3460 } 3461 } 3462 return(1); 3463 3464 } 3465 example 3466 { 3467 "EXAMPLE:"; echo = 2; 3468 list h_inj = 1,2,4,10,17; 3469 is_h_injective(h_inj,3); 3470 //1+2+4+10=17 3471 is_h_injective(h_inj,4); 3472 } 3473 3474 proc is_fix_injective(list a) 3475 "USAGE: is_fix_injective(a) 3476 RETURN: 1 if a is fixinjective, 0 otherwise 3477 EXAMPLE: is_fix_injective; shows an example; 3478 " 3479 { 3480 //Generation of the listlistlist 3481 list subsetlist = set_subset_set(a); 3482 list alreadycreatedlist; 3483 list listoflists; 3484 list emptylist1; 3485 list worklist; 3486 int i; 3487 int v; 3488 list checklist; 3489 int calculator; 3490 3491 int set_destination; 3492 3493 //create list of lists wich contain the lists of a certain length as elements 3494 for (i = 1; i<= size(subsetlist); i++) 3495 { 3496 //Determine the size of the acutal list to choose where to insert it in the listoflists 3497 set_destination = size(subsetlist[i]); 3498 if (set_contains(alreadycreatedlist,set_destination)==1) 3499 { 3500 //There is already an element with the same set size, so just insert it 3501 listoflists[set_destination] = insert(listoflists[set_destination],subsetlist[i]); 3502 } 3503 else 3504 { 3505 //There is not yet an element with the same set size, so create a new one 3506 listoflists[set_destination] = insert(emptylist1,subsetlist[i]); 3507 alreadycreatedlist = set_insert(alreadycreatedlist,set_destination ); 3508 } 3509 } 3510 3511 //Check for injectivity of each seperate list. Works as in injectivity or hinjectivity 3512 for (v=1; v<=size(listoflists); v++) 3513 { 3514 worklist = listoflists[v]; 3515 3516 checklist=calculate_max_sum(worklist[1]); 3517 for (i=2; i<=size(worklist); i++) 3518 { 3519 calculator = calculate_max_sum(worklist[i]); 3520 if (set_contains(checklist, calculator)==1) 3521 { 3522 return(0); 3523 } 3524 else 3525 { 3526 checklist = insert(checklist,calculator); 3527 } 3528 } 3529 } 3530 return(1); 3531 } 3532 example 3533 { 3534 "EXAMPLE:"; echo = 2; 3535 //this is fixinjective because 17=10+2+4+1 with different numbers of addens. 3536 list fix_inj = 1,2,4,10,17; 3537 //this is not fixinjective because 4+1=2+3. 3538 list not_fix_inj = 1,2,3,4; 3539 is_fix_injective(fix_inj); 3540 is_fix_injective(not_fix_inj); 3541 } 3542 3543 proc three_elements(list out, int iterations) 3544 "USAGE: three_elements(out, iterations) 3545 RETURN: Injective_knapsack created with the three elements method 3546 EXAMPLE: three_elements; shows an example; 3547 " 3548 { 3549 int a; 3550 int b; 3551 int c; 3552 int subsum; 3553 int adden = 1; 3554 int condition = 0; 3555 out = set_turn(out); 3556 if (is_injective(out)==0) 3557 { 3558 return(0); 3559 } 3560 else 3561 { 3562 for (int i=1; i<=iterations; i++) 3563 { 3564 while(condition==0) 3565 { 3566 subsum = calculate_max_sum(out); 3567 a = 2*subsum+adden; 3568 b = a+subsum+adden; 3569 c = b+subsum+1; 3570 if ((a+b)>(c+subsum)) 3571 { 3572 condition=1; 3573 } 3574 else 3575 { 3576 adden++; 3577 } 3578 } 3579 adden =1; 3580 condition=0; 3581 out=set_insert(out, a); 3582 out=set_insert(out, b); 3583 out=set_insert(out, c); 3584 } 3585 return(out); 3586 } 3587 } 3588 example 3589 { 3590 "EXAMPLE:"; echo = 2; 3591 //this is fixinjective because 17=10+2+4+1 with different numbers of addens. 3592 list super_increasing = 1,2,4,10,20; 3593 list a = three_elements(super_increasing,2); 3594 a; 3595 is_injective(a); 3596 } 2073 3597 /* 2074 3598 //===============================================================
Note: See TracChangeset
for help on using the changeset viewer.