Leandro Marin
email: leandro@um.es

Antonio J Jara
email: jara@um.es

Antonio F G Skarmeta
email: skarmeta@um.es

Shifting Primes: Extension of pseudo-Mersenne primes to optimize ECC for MSP430-based Future Internet of Things devices

Keywords: Security, 6LoWPAN, ECC, pseudo-Marsenne primes, shifting prime, Internet of Things

Security support for small and smart devices is one of the most important issues in the Future Internet of things, since technologies such as 6LoWPAN are opening the access to the real world through Internet. 6LoWPAN devices are highly constrained in terms of computational capabilities, memory, communication bandwidth, and battery power. Therefore, in order to support security, it is necessary to implement new optimized and scalable cryptographic mechanisms, which provide security, authentication, privacy and integrity to the communications. Our research is focused on the mathematical optimization of cryptographic primitives for Public Key Cryptography (PKC) based on Elliptic Curve Cryptography (ECC) for 6LoWPAN. Specifically, the contribution presented is a set of mathematical optimizations and its implementation for ECC in the 6LoWPAN devices based on the microprocessor Texas Instrument MSP430. The optimizations presented are focused on Montgomery multiplication operation, which has been implemented with bit shifting, and the definition of special psudo-Marsenne primes, which we have denominated "shifting primes". These optimizations allow to implement the scalar multiplication (operation used for ECC operations) reaching a time of 1, 2665 seconds, which is 42, 8% lower of the reached by the state of the art solution TinyECC (2, 217 seconds).

Introduction

Security is one of the major issues for the current digital society. The evolution of hardware technologies with the development of new devices such as wireless personal devices, embedded systems and smart objects, and the evolution of the services with the definition of cloud computing, online services, and ubiquitous access to the information are defining an extension of the capabilities of the current Internet, what make feasible to connect to Internet the objects and devices which are found surround us, it is the so-called Internet of things (IoT). IoT allows that systems can get a total control and access to another systems for leading to provide ubiquitous communication and computing. Thereby a new generation of smart and small devices, services and applications can be defined.

These small and smart things with connectivity and communication capacity from the IoT are what can be found, since some years ago, in the Low-power Wireless Personal Area Networks (LoWPANs). IETF 6LoWPAN working group has defined, in the RFC4944 [START_REF] Montenegro | Transmission of IPv6 Packets over IEEE 802[END_REF], the standard to support IPv6 over that LoW-PANs (6LoWPAN), in order to provide the technological basis for extending the Internet to small devices. 6LoWPAN offers to the LoWPANs advantages from the Internet Protocol (IP) such as scalability, flexibility, ubiquity, openness, and end-to-end connectivity. It could be considered that 6LoWPAN devices are also empowered with derived IP protocols, i.e., protocols for mobility such as MIPv6, management such as SNMP, and security such as IPSec. However it is not feasible, since 6LoWPAN nodes are highly constrained in terms of computational capabilities, memory, communication bandwidth, and battery power.

Therefore, with the mentioned constrains, it is a challenge to implement and use the cryptographic algorithms and protocols required for the creation of security services. Nowadays, 6LoWPAN security is based on Symmetric Key Cryptography (SKC) which is directly supported by specific hardware in the microprocessor. SKC is suitable to offer local solutions, such as were originally designed these personal area networks and local solutions such as location [START_REF] Nobles | Improved Estimation of Trilateration Distances for Indoor Wireless Intrusion Detection[END_REF], but for the future internet, it is required a higher scalability. For that reason, Public Key Cryptography (PKC) needs to be supported, Specifically, our research is focused on Elliptic Curve Cryptography for 6LoWPAN devices based on MSP430.

The MSP430 has been chosen since it is one of the most extended microprocessors in the Internet of Things devices and embedded systems. It is used for 6LoWPAN devices such as the Tmote Sky, for active Radio Frequency Identification (RFID) [START_REF] Zampolli | Ultra-low-power components for an RFID Tag with physical and chemical sensors[END_REF], and new hybrid technologies such as DASH7 [START_REF] Norair | DASH7: ultra-low power wireless data technology[END_REF].

The mathematical optimization of cryptographic primitives has been widely mentioned from a general point of view, and also for constrained devices. An overview of the state of the art is carried out in Section 2. From all the related works, TinyECC [START_REF] Liu | TinyECC: A Configurable Library for Elliptic Curve Cryptography in Wireless Sensor Networks[END_REF] is one of the most relevant references about ECC implementations for devices such as the based on MSP430. TinyECC chose Barret algorithm for reduction modulo p, but it has been demonstrated, in our previous work [START_REF] Ayuso | Optimization of Public Key Cryptography (RSA and ECC) for 8-bits Devices based on 6LoWPAN[END_REF], that Montgomery multiplication is more suitable for these devices.

In this paper is presented an evolution of the mentioned previous work with the inclusion of special primes, which reduce almost to the half the cycles needed for Montgomery multiplication. The selection of special primes is a very extended technique, for example in FIPS 186-3 are recommended special primes for elliptic curve, called generalized Mersenne numbers, for which modular arithmetic is optimized for processors that use 32 or 64 bits operations, see [START_REF] Locke | FIPS PUB 186-3: Digital Signature Standard (DSS)[END_REF]Section D.2]. Our advance has been to determinate the ideal primes for Montgomery multiplication based on the optimizations defined for 16-bits microprocessors.

In conclusion, this paper proposes an implementation of multiplication operation for ECC based on bit shifting, presented in Section 3, instead of the micro-processor's multiplication operation for microprocessor, which has not hardware support for multiplication operation such as MSP430. In addition, this has defined specific pseudo-Mersenne primes, which offer a simplification of the Montgomery multiplication implementation based on bit shifting, which have been denominated shifting primes, presented in Section 4. Finally, all the optimizations are implemented in Section 5, and evaluated in Section 6.

Related works

The usual solutions for WSNs are based on Symmetric Key Cryptography (SKC), but it is not suitable for the Future Internet of Things, since it is not scalable. SKC requires that both the origin and destination share the same security credential (i.e. secret key), which is utilized for both encryption and decryption. As a result, any third-party that does not have such secret key cannot access the information exchange. The majority of WSNs, included 6LoWPAN, are based on the IEEE 802.15.4 standard, which offers three levels of security: Hash Functions, Symmetric Key Cryptography and both [8].

This work is focused on Public Key Cryptography (PKC), also known as asymmetric cryptography, which is useful for secure broadcasting and authentication purposes, and this satisfies the scalability requirements from the Future Internet of Things. It requires of two keys: a key called secret key, which has to be kept private, and another key named public key, which is publicly known. Any operation done with the private key can only be reversed with the public key, and vice versa. These primitives provide the confidentiality, integrity, authentication, and non-repudiation properties.

Public Key Cryptography was considered unsuitable for sensor node platforms, but that assumption was a long time ago. The approach that made PKC possible and usable in sensor nodes was Elliptic Curve Cryptography (ECC), which is based on the algebraic structure of elliptic curves over finite fields. Some studies has been carried out about RSA in reduced chips [START_REF] Gura | Comparing Elliptic Curve Cryptography and RSA on 8-bit CPUs[END_REF], but it was non-viable. Therefore, PKC for small and smart devices is mainly focused on ECC, since ECC presents lower requirements both in computation and memory storage, due to its small key sizes and its simpler primitives [START_REF] Hitchcock | Implementing an efficient elliptic curve cryptosystem over GF(p) on a smart card[END_REF].

The related works of the implementation of an efficient cryptographic algorithm for constrained devices have been focus on the optimizations of the multiplication operation, since it is the most expensive operation in RSA and ECC algorithms. ECC implementation can be over either GF (2 m ) or GF (p), we have focused on modular arithmetic, i.e. GF (p), since this has similar nature to the arithmetic of the micro-controller used in the 6LoWPAN devices. However, some interesting approaches have been defined for ECC implementations over GF (2 m ), for example [START_REF] Uhsadel | Enabling Full-Size Public-Key Algorithms on 8-bit Sensor Nodes[END_REF] has showed that field multiplication is faster over GF (2 m ) than in GF (p) for new suggested hardware implementations, where the instructions set and arithmetic of the micro-controller are closer to GF (2 m ). Some of the most known software implementations over modular arithmetic for ECC are TinyECC [START_REF] Liu | TinyECC: A Configurable Library for Elliptic Curve Cryptography in Wireless Sensor Networks[END_REF][START_REF] Seo | TinyECCK: Efficient Elliptic Curve Cryptography Implementation over GF(2m) on 8-bit MICAz Mote[END_REF] and NanoECC [START_REF] Szczechowiak | NanoECC: Testing the Limits of Elliptic Curve Crytography in Sensor Networks[END_REF], which implement ECC-based operations. TinyECC adopted several optimization techniques such as optimized modular reduction using pseudo-Mersenne primes, sliding window method, Jacobian coordinate systems, in-line assembly and hybrid multiplication in order to achieve computational efficiency. Realise, that the computational and memory requirements of these algorithms are not small (e.g. signature requires 19308 bytes ROM and 1510 bytes RAM for the MICAz, generating a signature in 2 seconds. and verifying it in 2.43 seconds), although the implementation of these primitives is constantly evolving and improving.

Mathematical optimization based on bit shifting instead of microprocessor's multiplication operation

There is an important literature about the advantages of the Montgomery's representation for this calculation [START_REF] Ayuso | Optimization of Public Key Cryptography (RSA and ECC) for 8-bits Devices based on 6LoWPAN[END_REF][START_REF] Cohen | Efficient Elliptic Curve Exponentiation[END_REF][START_REF] Cohen | Efficient Elliptic Curve Exponentiation Using Mixed Coordinates[END_REF]. For that reason, it is used for both solutions i.e. based on bit shifting and multiplication operation. The original details of the Montgomery's representation for can be found in [START_REF] Montgomery | Modular Multiplication Without Trial Division[END_REF], although many other books or papers refer to it. Our solution is based on ECC, which requires an integer size (k) of 160-bits, i.e. k = 160, R = 2 160 ). Montgomery representation has been chosen instead of other solutions, such as the Barrett reduction used in TinyECC [START_REF] Liu | TinyECC: A Configurable Library for Elliptic Curve Cryptography in Wireless Sensor Networks[END_REF], since in Montgomery representation, the representation of the numbers a and b, which are going to be multiplied, are aR and bR mod n (n is a prime for ECC). Addition and subtraction operations with these numbers do not cause problems since R is common factor. The problem is coming with the multiplication operation, when aR and bR is multiplied, the result is abR 2 , but what is required is abR. Therefore, it needs to be reduced by factor R. The great advantage of Montgomery representation is to carry out the reduction of the factor R during multiplication,

The multiplication operation is what consumes the higher part of the time, since it is repeated thousands of times. For that reason, it is the part optimized and discussed more in detail in the next subsections.

Bit shifting

Let a and b two integers in Montgomery representation. Then, aR and bR mod n between 0 and n -1. They are stored in binary representation, i.e. aR = i a i 2 i and bR

= i b i 2 i . It is calculated (aR)(bR)R -1 = (ab)R, therefore it is required to carry out k right bit shifting (with k = 160).
Since that, modulus n is odd, because it is a prime in ECC. Thus, when it is divided by 2 mod n, two options are defined: either it is even number and it can be directly shifted, or it is odd number and consequently needs to add n, in order to reach 0 in the least significant bit, in order to be able to shift it.

Multiplication process requires a variable to accumulate the current result, we will call to that variable P , whose digits are P = i P i 2 i . Each one of the digits B i is multiplied by i A i 2 i and divided by 2. As initially P is 0, if B i = 0 for some initial values, it can be ignored. Therefore, this starts directly by the digit in the position i 0 , such that B i0 = 1, and copy the value of A i in P i .

From the position i 0 , we can find in the next steps: B i = 0 or 1. On the one hand, when B i = 0, it divides P by 2, and add n when P is odd. On the other hand, when B i = 1, then it adds the value of aR to P , before it is divided by 2.

To make a first estimation of the time, we consider that the probability to find B i = 1 or 0 is the same, i.e. 0, 5. Therefore, for each k bits of B i , when it is 1, it needs to carry out an addition of k bits (i.e. addition of a i ) and a division by 2 of P . Otherwise, when it is 0 only one right bit shifting is required. Therefore, k divisions by 2 and k/2 additions. Since, each division by 2 is always a shifting and, with probability 0.5, is also an addition of n. Therefore, the total time is:

k(d + s/2) + (k/2)s = k(d + s),
where d is the time for k right bit shifting, and s is the time for k bits addition.

Microprocessor MSP430 offers 16-bits operations. Therefore, additions and bits shifting are carried out in blocks of 16 bits. α is the time for 16-bits additions and shifting (usually 1 to 4 CPU cycle for bit shifting and 1 to 6 cycles for additions, depends on access to memory and registers). The final time is:

2αk 2 /16 = αk 2 /8.
The program code of the bit shifting algorithm is presented in the Algorithm 1. This has been programmed in assembler code with the other presented optimizations. The assembled code is based on MSPGCC.

Microprocessor's multiplication operation

Let an instruction from the microprocessor's set of instructions to carry out multiplication operation, which operates 2 registers of 16-bits and save the 32bits of the result in two registers of 16-bits. This instruction is simulated in MSP430 chip, in [17, page. 478-480]. It is called µ to the time spent by that operation, and α for the time of 16-bits additions and 16-bits shifting.

Let the next numbers to apply the multiplication aR = j A j 2 16j and bR = j B j 2 16j . In this case, j values are between 0 and k/16, instead of between 0 and k. Therefore, for each multiplication of k bits, it needs to carry out k/16 16-bits multiplications and 2k/16 additions, getting the results in a variable of k + 16-bits. Therefore, the time is equal to: (µ + 2α)k/16.

For each step of the multiplication of aR and the digits of B i , since multiplication is carried out in blocks of 16-bits, this needs to add the current result with the previous one i.e. an addition of (a sum of two numbers k bits and 16 bits. Thus, α(k + 1)/16 additions), then it needs to divide it by 2 16 mod n. It is called δ to the time used for the division by 2 16 .

The total time for each one of the 16 bits blocks (k/16 blocks,

B i ) is (µ + 2α)k/16 + α(k + 1)/16 = µk+α(3k+1)

16

, and addition δ, i.e. the total time is:

µk 2 +α(3k+1)k 256 + kδ 16 .
Division of a number of k + 16 bits by 2 16 mod n is carried out adding n until that the result is multiple of 2 16 . If the last digit of n in base 2 16 is 1 the process is simple, since the number of times to subtract n is indicated by the last digit of the number to be divided by 2 16 mod n. Therefore the total time is:

δ t = (µ+3α)k+α 16 .
δ t is the ideal time, when n has been chosen such that its last digit is equal to 1, in order to carry out in a simple way the division. In a general case, it cannot be assumed that the value of the last digit of n is equal to 1, thus this estimation is not realistic. But, Extended Euclidean algorithm can be used, in order to fix the process pre-calculating the modular multiplicative inverse of the last digit of n mod 2 16 and it can be used with the last digit of p. Therefore, it is reached a more realist time:

δ = k 16 (µ + 3α) + 2µ + 2α.
This can be simplified considering that terms without k are not highly relevant for the total time. Therefore δ t and δ are very similar, in the order of k 16 (µ + 3α). Therefore, based on that expression and reducing terms that do not have k 2 , the total time for microprocessor's multiplication operation is:

M µk 2 256 + (µ+3α)k 2 256 = (2µ+3α)

Comparative between bit shifting and microprocessor's multiplication operation

The comparative between bit shifting and microprocessor's multiplication operation shows us that in a general way bit shifting is better than microprocessor's multiplication operation, when the following equation is true:

αk 2 8 < (2µ+3α)k 2 256 ⇒ 32α < 2µ + 3α ⇒ 29 2 < µ α .
In conclusion, when the number of cycles to carry out microprocessor's multiplication operation is more than 15 times the cycles to carry out addition or bit shifting, it is preferable bit shifting solution. Since, MSP430 microprocessor's multiplication operation requires a big amount of clock cycles (150 cycles in the MSP430), while the bit shifting and additions only needs between 1 and 4 cycles for bit shifting and 1 and 6 cycles for addition, this depends on the access to registers and memory, i.e. rrcR4, i.e. bit shifting for registers is just 1 cycle, but rrc0(R1), which is bit shifting in the memory address with value R1 are 4 cycles. The evaluation has presented that bit shifting is better than microprocessor's multiplication operation with a relation of when its cost is 15 times or less than multiplication i,e, µ < 15α, and MSP430 has a µ/α between 38 and 150.

Shifting primes

Shifting primes are special pseudo-Mersenne primes for bit shifting Montgomery multiplication. They have been defined under this work to optimize them for the bit shifting implementation presented in the Section 3. The shifting primers are formally defined as: Definition 1. It is said that p is a shifting prime (of type α and λ), if p is a prime and exists u such that:

p = u • 2 λ-α+1 -1 and 2 α-2 < u < 2 α-1 .
The parameter α denotes the length of the word for addition and λ the length of the prime number. Our work is focused on the case α = 16 and λ = 160, i.e. ECC with 160-bits key length in our MSP430-based 16-bits microprocessor. Notice that if 2 α-2 < u < 2 α-1 then 2 α-2+λ-α+1 -1 < p < 2 α-1+λ-α+1 -1. Therefore, 2 λ-1 -1 < p < 2 λ -1 and then p is λ-bits length.

The number of shifting primes depends on λ and α. For example, for α = 8 and λ = 160 there is only one (with u = 100). For α = 16 and λ = 160 there are 288 shifting primes.

The basic operations based on these special primes (shifting primes) for the Montgomery multiplication presented in the Section 3 are presented in the next subsection.

Basic operations

In order to implement the basic operations, it has been considered, in addition to the mentioned, the next optimizations.

On the one hand, the points and coordinates, for an elliptic curve E over a field is a nonsingular cubic curve, are defined over the projective plane. It has been considered the field Z p with p a 160 bits prime, and E in Weierstrass normal form, E : y 2 = x 3 + ax + b. It has been considered the special case with a = -3, which reduces the amount of operations. There are different coordinate systems that can be used to represent the points. We consider the mixed coordinate system considered in [START_REF] Cohen | Efficient Elliptic Curve Exponentiation Using Mixed Coordinates[END_REF] for which the basic time for scalar multiplication is 1610.2M with M the time for a basic 160 bits modular multiplication mod p, our focus in our research is optimize modular multiplication, since scalar multiplication is based on this.

On the other hand, all the operations are implemented in assembler, where one of the main decisions has been to use 10 registers to store a number (called the accumulator) in which we make the basic bit shifting and additions. This decision makes that only 2 registers are available for other operations, but it is worth, since operations with the accumulator are very fast, and when the accumulator is combined with the shifting primes, the result is also very quick.

Following the same methodology defined in the Section 3, there are three main operations in Montgomery multiplication:

Division by 2 The most basic operation for Montgomery multiplication is

x → x • 2 -1 in Z p . Suppose x = x 0 + x 1 • 2 16 + • + x 9 • • • 2 16•9 < p.
The usual algorithm for this operation is as follows: if x is even then result is shifting x one position to the left. else result is x + p shifted one position to the left. end if Even when is being used the accumulator, it is needed 3 cycles to check if x is odd and jump depending on it. Once we have decided that, it is needed 10 cycles to shift the accumulator in the best case, and 30 cycles to add a general prime p and shift. This makes that this algorithm for a general prime requires between 13 and 33 cycles with an optimal programming.

The algorithm for shifting primes is: shift x if no carry (i.e. if x was even) then jump to (END), because the result is already in x. end if ignore the carry and add u to the most significant word of x. (END) The result is in x The result is clear when x is even. In case x is odd, if this shifts x, then this gets (x -1)/2 and this requires (x + p)/2. But, if u is added to the most significant word of x, then the result reached is

(x -1)/2 + u • 2 λ-α = x -1 + u • 2 λ-α+1 2 = x + p 2
It is exactly the result required. This is the advantage from the shifting primes.

The number of cycles for this operation with this optimization is equal to: 10 cycles to shift x, 2 cycles for the jump, and another 2 cycles in case that it is required to add u. Realise, that when x is between 0 and p, then (x + p)/2 is also between 0 and p, and consequently it is not required any additional correction. The total number of cycles is 12 in the even case and 14 in the odd case. This reduction is significant because this operation should be done λ times for a Montgomery multiplication. Since, the probability for odd x is 0.5 the usual algorithm would give 13 • 0.5 + 33 • 0.5 = 23 cycles and the one with shifting primes 13 cycles. Therefore, a reduction of the 43, 47% of the cycles is reached.

Addition and correction modulo p Montgomery multiplication algorithm requires to add the second operand to the accumulator depending on the value of the bits of the first operand. In order to to keep the result between 0 and p -1, when the addition is over this quantity, it is required to make a correction, i.e. subtract p, to offer the result inside the range.

Adding a λ-bits variable to the accumulator requires a lot of cycles, because the variable should be in memory. Specifically, it is required 10 additions add(c).w mem,reg, where for each addition are required 3 cycles. Therefore, the whole addition 30 cycles.

The correction for a general prime requires to compare the result with the prime. In order to do it, this compares the significant word of the accumulator with the most significant word of the prime (2 cycles), and then a jump (2 cycles) is carried out to different places, depending on the result. There are two cases in which the problem is clear (if the numbers are not equal). If they are equal, then it needs to check the following values, since it is possible to require a correction or not.

The mentioned correction is simpler in the case of shifting primes since:

Proposition 1. Let p be a shifting prime p = u•2 λ-α+1 -1 and a = λ/α-1 i=0
a i 2 αi the accumulator after a partial sum in the Montgomery multiplication of x and y. Then:

1. a cannot be exactly p. 2. a needs no correction if and only if the most significant word of a is under 2u.

Proof.

1. In Montgomery multiplication, the accumulator has partial products h • y.

If y = 0 the partial products cannot be 0 (or p, that is the same element in Z p ) and in case y is 0, the partial result would be always 0, not p. 2. The accumulator needs correction if and only if a ≥ p, that using (1) is equivalent to a > p. Let k = λ/α -1. Then:

a = k i=0 a i 2 αi = a k 2 λ-α + k-1 i=0 a i 2 αi p = 2u2 λ-α -1
The number k-1 i=0 a k 2 αi is between 0 and 2 λ-α -1 because it is written with k -1 words. Therefore:

a > p ⇔ a k 2 λ-α + k-1 i=0 a i 2 αi > 2u2 λ-α -1 ⇔ (a k -2u)2 λ-α > - k-1 i=0 a i 2 αi + 1 The number - k-1 i=0 a i 2 αi + 1 is negative, therefore if a k -2u ≥ 0 we have a > p. Conversely, if a k -2u < 0 then a k -2u ≤ -1. Therefore: (a k -2u)2 λ-α ≤ -2 λ-α ≤ - k-1 i=0 a i 2 αi + 1 .
This has been proved that the result needs correction if a > p and this is equivalent to a k ≥ 2u. Then correction is required if and only if a k < 2u.

Addition with shifting and correction modulo p Following the Montgomery multiplication algorithm, this requires after the addition, a shifting for the following loop. It is usually better to consider both operations together because we can reduce the number of cycles avoiding a partial correction.

Suppose a is the accumulator and it required to calculate (a + w)2 -160 (p). The algorithm is the following: add w to a from right to left shift a from left to right with carry without previous correction. if no carry then jump to (END) end if compare u with the most significant word of a. if u is less than it then add u to the most significant word of a and jump to (END) end if sub u to the most significant word of a and add 1 to the final result.

Assembler implementation and execution times

The previous algorithms and optimizations are implemented in the MSP430 with the following conventions: It is used the register R5 for u, R4 for the address of the operand, and 10 registers for the accumulator R6, R7, ..., R15. In DIV2 it is needed that the carry flag is 0 before executing these instructions. Therefore, an extra instruction CLRC is required to clear the carry bit.

DIV2

The execution time is 12 cycles, when no carry and 13 cycles in the other case (probability 0.5). Therefore, this code needs 12.5 cycles.

In modADD R4, it is needed 30 cycles for the addition to the accumulator, 2 cycles to check if there is carry overflow. The probability of correction is around 0.5, therefore we are going to calculate both cases. If there is no correction, then it compares R6 with 2u (2 cycles) and jump to the end (2 cycles). This is equal to 30 + 2 + 2 + 2 = 36 cycles. Otherwise, when correction is required, the highest probability if that carry bit is active after the addition, in that case, it is needed 30 + 2 + 1 + 2 + = 35 + cycles, where is a part of the code with very low probability. In conclusion, the average cycles needs for this code are 36 cycles.

modADD R4

ADD. w 1 8 ( R4 ) , R15 ADDC. w 1 6 ( R4 ) , R14 ADDC. w 1 4 ( R4 ) , R13 ADDC. w 1 2 ( R4 ) , R12 ADDC. w 1 0 ( R4 ) , R11 ADDC. w 8 ( R4 ) , R10 ADDC. w 6 ( R4 ) , R9 ADDC. w 4 ( R4 ) , R8 ADDC. w 2 ( R4 ) , R7 ADDC. w 0 ( R4 ) , R6 JC reqC CMP. w R6 , 2 u JL end reqC :

SUB . w 2u , R6 ADD. w #1,R15 JNC end ADD. w #1,R14 ADDC. w #0,R13 ADDC. w #0,R12 ADDC. w #0,R11 ADDC. w #0,R10 ADDC. w #0,R9 ADDC. w #0,R8 ADDC. w #0,R7 ADDC. w #0,R6 end :

modADD+DIV2 R4

ADD. w 1 8 ( R4 ) , R15 ADDC. w 1 6 ( R4 ) , R14 ADDC. w 1 4 ( R4 ) , R13 ADDC. w 1 2 ( R4 ) , R12 ADDC. w 1 0 ( R4 ) , R11 ADDC. w 8 ( R4 ) , R10 ADDC. w 6 ( R4 ) , R9 ADDC. w 4 ( R4 ) , R8 ADDC. w 2 ( R4 ) , R7 ADDC. w 0 ( R4 ) , R6 RRC . w R6 RRC . w R7 RRC . w R8 RRC . w R9 RRC . w R10 RRC . w R11 RRC . w R12 RRC . w R13 RRC . w R14 RRC . w R15 JNC end CMP. w R5 , R6 JNC p r e SUB . w R5 , R6 ADD. w #1,R15 JNC end ADD. w #1,R14 ADDC. w #0,R13 ADDC. w #0,R12 ADDC. w #0,R11 ADDC. w #0,R10 ADDC. w #0,R9 ADDC. w #0,R8 ADDC. w #0,R7 ADDC. w #0,R6 JMP end p r e : ADD. w R5 , R6 end :

In conclusion, it is required addition and shift. If the accumulator is even (probability is 0.5), then it is required 42 cycles, else it is 4 cycles in case that is required to add p and 7 + in case that it has that subtracts p. Therefore, the final cost is 42 + 0.5(4 + 0.5(3 + )) ≡ 45 cycles.

Bit shifting and shifting primes

The Section 4 has described the advantages for the Montgomery multiplication with the defined shifting primes. This section describes the union of the presented bit shifting implementation in the Section 3 and the mentioned shifting primes. Finally, some additional optimizations have defined for the whole process. The operations on elliptic curves have been studied extensively and optimized for very different architectures. The basic operation with elliptic curves is the scalar multiplication n × P , where P is a point on the curve, and n is a number of large size. This operation is deeply analysed in [START_REF] Cohen | Efficient Elliptic Curve Exponentiation Using Mixed Coordinates[END_REF], where is defined that the cost of the scalar multiplication for primes of 160-bits requires 1610, 12 modular multiplications of 160-bit numbers. Therefore, modular multiplication is what is being optimized in this work.

Such as mentioned in the related works, Section 2, there are several alternatives for the implementation of the modular multiplication. For example, TinyECC solution is based on Barrett reduction [START_REF] Liu | TinyECC: A Configurable Library for Elliptic Curve Cryptography in Wireless Sensor Networks[END_REF]. For our solution, it has been chosen Montgomery representation, since this is more suitable to exploit the advantages from the shifting primes.

Let x and y, which are the multiplication operands and p, a shifting prime for a determined u.

A basic implementation of the Montgomery multiplication with the shifting primes requires the following steps:

1. Traverse bit by bit the operand x. 2. If it is found a bit with value equal to 0, then the accumulator is rotated, i.e. (operation DIV2). 3. Otherwise, if it is found with value equal to 1, then y is added to the accumulator and the accumulator is also rotated (operation modADD+DIV2).

The cost of the operations DIV2 and modADD+DIV2 have been already mentioned in the Section 4.

For traversing x bit by bit has been used the next registers:

-10 registers R6,R7,...,R15.

-1 register to store u.

-1 register to read the word of which is being traversed of x. Notice, that x is composed by 10 words of 16 bits. -In order to access to the right word of x, it is stored in the stack memory the address of the last word which has been access of x increased in 2 memory units, in order that it is pointing to the next word of x. -In addition, it is also stored in the stack memory the address from the first word of x. -At the beginning of the loop to traverse the operand x, it is stored in the register R5 the address of the first word of x, and then is used the following code.

MOV. w 0 ( R5 ) , R5 SETC RRC R5

This code introduces a bit of control, which allows us to rotate the register until that the result is equal to 0. When, the result is 0, that bit is ignored, since it was introduced by us, with the presented code. Then, it is read the next word of x. This technique allows to avoid the use of a counter to control when the register has been fully traversed. For example, an example where is used that method is the next code, which shows how to find the first bit which is equal to 1 of x. The jump to end0 is defined to finish returning the value 0, since it has read all the operand and it has not been found any bit set to 1. The total number of cycles is until 17 cycles for jumping to another word, considering that this operation is required for each new word (i.e. each 16 bits), it can be considered that is introduced 1.7 cycles by each bit of the operand.

Considering that the probability to find a bit set to either 1 or 0 are equal to 0.5, it is obtained the following time:

1. If the bit is 1, then it is required 3 cycles to check it. In addition, it needs to be checked the control bit, i.e. 2 additional cycles, and carry out an addition with rotation, which are 45 cycles. In total 50 cycles with probability 0.5. 2. Otherwise, if the bit is 0, it is also required 3 cycles to check it, and 15.5 cycles to rotate it. In total 18.5 cycles with probability 0.5. 3. Therefore, the mean number of cycles per bit is equal to 25 + 9.25 = 34.25. 4. To the mentioned mean number of cycles needs to be added a jump, and the checking of end of world. In total is equal to 38. 5. This mean number of cycles per bit needs to be multiplied by 160 bits.

Therefore, this results 6080 cycles, in addition this requires some pre-calculus and function callings, that we have estimated in 6293 cycles. This results with a clock speed equal to 8 Mhz from the MSP430, 1610 • 6293/8 • 10 6 = 1.2665 seconds.

This implementation offers better results than other implementations based on other types of primes. For example, notice that this operation with TinyECC has a cost to encrypt or decrypt, where is used the scalar multiplication of 3, 271 seconds and 2, 217 seconds respectively. These operations can be carried out with our implementation in around 1, 2665 seconds with shifting primes.

Results and Evaluation

The evaluation of the algorithms optimized has been initially simulated over our own developed simulator, which verifies the results with the cryptographic library LiDIA, and finally evaluated over real motes, specifically over Tmote Sky with the Contiki 2.4 OS, where is defined a set of functions with assembler code inline.

The quickest ECC algorithm is based on Montgomery + window method, see [START_REF] Cohen | Efficient Elliptic Curve Exponentiation Using Mixed Coordinates[END_REF][START_REF] Ayuso | Optimization of Public Key Cryptography (RSA and ECC) for 8-bits Devices based on 6LoWPAN[END_REF]. This has been optimized for MSP430 with bit shifting in assembler language for the Montgomery multiplication of 160 bits and for the arithmetic advantages from the defined shifting prime. Modular Montgomery multiplication is carried out in 6293 cycles, and consequently scalar Montgomery in around 1610 times the modular Montgomery multiplication. The time reach, considering the 8 Mhz MSP430 microprocessor found in the Tmote Sky, is: 1610 • 6293/8 • 10 6 = 1.2665 seconds.

In order to reach this solution, we have used 10 microprocessor's registers to keep the 160 bits variable (the accumulator) with the partial multiplication results, with this optimization we have reduced almost the 40% of the total number of cycles, since rrc operation for bit shifting, and add operation for addition spend 1 cycle and 3 cycles respectively, instead of 4 and 6. In addition, loops have been unrolled in order to optimize more the final assembler code. Finally, such as special primes have defined in order to optimize the modular Montgomery multiplication, moving from a number of cycles for 12480 following the optimization from the Section 3 to 6293 cycles, i.e. from around 2, 5 seconds similar to TinyECC, which lower time is 2, 217 seconds to 1, 2665 seconds which is a 42, 8% lower than TinyEcc and our previous work [START_REF] Ayuso | Optimization of Public Key Cryptography (RSA and ECC) for 8-bits Devices based on 6LoWPAN[END_REF].

Conclusions and Future Work

Future Internet of Things is defining a new set of challenges in order to offer security support, since technologies such as 6LoWPAN offers Internet connectivity to small and smart devices with highly constrained resources. Therefore, it is necessary to provide efficient, scalable, and suitable security mechanisms. For that reason, it is required Public Key Cryptography (PKC). This work has evaluated and optimized Elliptic Curve Cryptography (ECC) implementation for Future Internet of Things devices based on the Texas Instrument MSP430 microprocessor, which is used for several Future Internet of Things devices.

The optimizations for ECC are based mainly on bit shifting implementation of the modular Montgomery multiplication, and in a special type of primes (shifting primes) defined under this work, which offer a set of arithmetic advantages for the implementation of the bit shifting based modular Montgomery multiplication.

The result reached with the mentioned optimizations is 1, 2665 seconds for the scalar Montgomery multiplication, which reduces a 42, 8%, with respect to the TinyECC implementation which offers a result of 2, 217 seconds. Therefore, it can be concluded, that with the reached time, ECC is suitable for the Future Internet of Things.

Finally remark, selection of special primes is a very well-known technique, which does not mean any vulnerability or weakness for our systems, e.g. standards such as FIPS 186-3 recommends specific elliptic curves for which modular arithmetic is simpler for 32 and 64 bits microprocessors. Therefore, our advance has been to determinate the ideal primes for Montgomery multiplication based on bit shifting operations and the 16-bits MSP430 microprocessor.

Ongoing work is focused on carry out additional optimizations based on reduction of the number of additions accessing to blocks of 4 bits in each step, instead of bit by bit, and the use of pre-calculated values.

  k 2

	256	.
	Algorithm 1 Code based on Bit shifting
	accumulator = 0
	for i = 0 to k do
	if Bi equals 1 then
	accumulator = accumulator + A
	end if
	if accumulator is odd then
	accumulator = (accululator + p)/2
	else
	accumulator = accumulator/2
	end if
	end for


Svetla Boytcheva

Galia Angelova

Zhivko Angelov

Dimitar Tcharaktchiev

Hristo Dimitrov

Integrating Patient-Related Entities using Hospital Information System Data and Automatic Analysis of Free Text

Keywords: automatic information extraction, secondary use of patient records, temporal aspects of data integration

The article presents research in secondary use of information about medical entities that are automatically extracted from the free text of hospital patient records. To capture patient diagnoses, drugs, lab data and status, four extractors that analyse Bulgarian medical texts have been developed. An integrated repository, which comprises the extracted entities and relevant records of the hospital information system, has been constructed. The repository is further applied in experiments for discovery of adverse drug events. This paper presents the extractors and the strategy of assigning time anchors to the entities that are identified in the patient record texts. Evaluation results are summarised as well as application scenarios which make use of the extracting tools and the acquired integrated repository.

Introduction

Electronic Health Record (EHRs) are viewed as the basic source of patient-related data, keeping all important medical information about each patient and (in a longer run) providing access to the complete patient history. The idea to re-use the EHR content beyond the direct health care delivery is relatively recent (published in 2007, its implementation is still in its infantry according to [START_REF] Prokosch | Perspectives for medical informatics. Reusing the electronic medical record for clinical research[END_REF]). EHR data can facilitate the clinical research and reduce substantially the cost of clinical trials as they provide an enormously large resource for statistical observations, comparative studies, quality evaluation, monitoring the effectiveness of public health services and so on. By default the Information Technologies (IT) are the only means to cope with the large data volumes, moreover EHRs are to be supported within IT environments which provide secure, confidential, and private data access. Therefore, it is important to design research prototypes where secondary EHR use demonstrates the potential of novel, IT-enabled developments for improving the clinical practice. This ambitious and challenging objective, however, faces the incompleteness, fragmentariness, inconsistency and vagueness of expressions in the established medical practices, which rely on domain and/or implicit knowledge to support the information interpretation. Patient-related data are recorded in various formats, encoded by numerous medical nomenclatures and classifications, with heterogeneous terminologies, specific national traditions to shape the patient record texts and so on. Much EHR information is presented as free text so the Natural Language Processing (NLP) is often viewed as an embedded technology that helps to extract structured knowledge chunks from the EHR texts. Current tasks related to secondary EHR use seem to be mainly focused on the extraction activities; there are fewer integration attempts which aim at the exploitation of the accumulated information.

This paper presents an experimental integration of patient-related clinical data in order to construct a repository for identification of Adverse Drug Events (ADE) in the PSIP project (Patient Safety through Intelligent Procedures in Medication) [START_REF]PSIP (Patient Safety through Intelligent Procedures in Medication)[END_REF].

Components for automatic extraction of entities from free text have been developed since much information is documented in Bulgarian hospitals as unstructured text. The article discusses specific solutions regarding time anchoring and harmonisation of data units while the automatically extracted entities are integrated with the Hospital Information System (HIS) records to form a unified patient case.

The article is structured as follows. Section 2 overviews related research. Section 3 presents the background of our experiment. Section 4 considers our approach to integration of all recognised entities, which are available as structured HIS values or are extracted by the text analysers. Event sequencing is important and we present our empirical strategy for assignment of temporal markers to all findings. Section 5 considers the evaluation results and discusses feasible application scenarios of the integrated repository given that it inevitably contains some inconsistencies and certain percentage of erroneous assignments. Section 6 contains the conclusion.

RELATED WORK

Data quality issues, related to secondary EHR use, are discussed in [START_REF] Botsis | Secondary Use of EHR: Data Quality Issues and Informatics Opportunities[END_REF]. The authors consider three categories of data quality: (i) incompleteness -missing information;

(ii) inconsistency -information mismatch between various or within the same EHR data source; and (iii) inaccuracy -non-specific, non-standards-based, inexact, incorrect, or imprecise information. The article [START_REF] Botsis | Secondary Use of EHR: Data Quality Issues and Informatics Opportunities[END_REF] reports about inconsistencies which are common to many data collections, e.g. 48% of the patients did not have corresponding diagnoses or disease documentation in the pathology reports. The suggestion is to develop software tools for automatic data validation and flexible data presentation in order to support information integrity. This recent article encourages us to continue our experiments despite the negative data quality findings in our training corpus; we apply the data quality categories introduced in [START_REF] Botsis | Secondary Use of EHR: Data Quality Issues and Informatics Opportunities[END_REF].

Rule-based automatic approaches for data extraction and integration ensure the state-of-the-art achievements in the construction of large scale resources (over 300 millions rows of data from three institutes are currently included in the Biomedical Translational Research Information System [START_REF] Cimino | The clinical research data repository of the US National Institutes of Health[END_REF]). The mapping rules are created manually based on human analysis, using a large dictionary of medical terminology.

Predefined queries are developed in the system to respond information needs. This article discusses various kinds of (potential) application of such an integrated resource which however is difficult to obtain as it requires long years of data collection.

Modelling of timelines is considered in [START_REF] Roque | A Comparison of Several Key Information Visualisation Systems for Secondary Use of EHR Content[END_REF] which overviews the six state-of-theart systems related to visualisation of temporal information in EHRs. Most of these systems operate on readily available lists of type-and time-tagged events. One of the systems identifies pre-defined classes of entities (e.g. diseases, investigations, problems, drugs, etc.) and semantic relationships between them (e.g. investigation indicates problem) in natural language texts [START_REF] Hallett | Multi-modal presentation of medical histories[END_REF]. Searching useful information with self-service visual query tool is implemented in repositories containing preliminary indexed full-text documents, e.g. the system STRIDE works on a clinical data warehouse containing information about over 1,3 million patients [START_REF] Lowe | STRIDE -An integrated standards-based translational research informatics platform[END_REF].

As our extractors perform free text analysis on the raw texts in the USHATE HIS, we briefly overview the recent achievements in the area.

We deal with the automatic assignment of ICD-10 diagnoses to free text phrases in Bulgarian language (ICD-10 is the International Classification of Diseases, version 10 [8]). A recent review [START_REF] Stanfill | A systematic literature review of automated clinical coding and classification systems[END_REF] summarises achievements in the automatic coding of English medical texts. The authors note that software tools for automating coding are "available but currently not widely used, most likely because the systems are still in development and their performance in production is unproven". Various evaluation metrics are summarised and the best result reported is 98% coding accuracy. We note that systems coding English medical texts are developed since more than 20 years; results for other natural languages are less precise; e.g. for French the agreement between the automatic procedure for assignment of ICD 10 codes and the EHR content is 21%, which is partly due to the fact that the diagnoses encoded in the hospital information systems often reflect financial considerations [START_REF] Chazard | Can F-MTI semantic-mined drug codes be used for Adverse Drug Events detection when no CPOE is available? Stud[END_REF].

Another important extraction task is the automatic recognition of drugs and dosages, which occur in the patient record texts. State-of-the-art results reported for English are: sensitivity/recall for drug names 88,5% and for dosage 90,8%; precision for drug names 91,2% and for dosage 96,6% [START_REF] Halgrim | Extracting medication information from discharge summaries[END_REF]. A measure that combines the sensitivity (recall) and the precision is their harmonic mean f-score; another highly successful extraction system is MedEx [START_REF] Xu | MedEx: a medication information extraction system for clinical narratives[END_REF] which extracts drug names with f-score 93,2%, and achieves f-scores 94,5% for dosage, 93,9% for route and 96% for frequency. The French Multi-Terminology Indexer F-MTI [START_REF] Chazard | Can F-MTI semantic-mined drug codes be used for Adverse Drug Events detection when no CPOE is available? Stud[END_REF] achieves very good results in drug extraction as well. Codes from the ATC (Anatomical Therapeutic Chemical) classification [START_REF]ATC drugs classification[END_REF] are automatically assigned to the extracted drug names.

The extraction of ATC codes from the free text of French discharge letters is performed with f-score 88% when compared to the manual extraction; however, compared to the Hospital Pharmacy content, the f-score is 49%. These figures are the baseline for assessment of our results in the automatic recognition of drugs in Bulgarian patient record texts.

The performance of information extraction from clinical texts gradually improves and exceeds 90% accuracy [START_REF] Meystre | Extracting Information from Textual Documents in the Electronic Health Record: A Review of Recent Research[END_REF]. In our experiments we have also developed different modules which focus on various text entities: patient status and values of clinical tests and lab data. These modules were implemented within a period of two years with progressive collection of the corresponding lexical and grammatical resources, leading to progressive improvement. The extractors were trained via specific procedures and can be applied as separate text analysis components. Our results are comparable to the state-of-the-art achievements in the area, see section 5.

RESEARCH CONTEXT

Our experiments in secondary use of EHR content are performed on training and testing corpora which contain anonymised hospital Patient Records (PRs).

USHATE -Clinical Settings

USHATE belongs to the oldest and largest Medical University in Bulgaria and is specialised mostly for treatment of endocrine and metabolic disease. Usually patients with such type of diseases have many complications and accompanying illnesses. In this way many patients arrive to the hospital with drugs prescribed elsewhere (in some other hospital, for instance, or at the ambulatory care, or from their GPs). Statistical observations show that the average number of drugs, discussed in a patient discharge letter in USHATE, is 5,4 drugs per hospital record. However, according to the Computerised Physician Order Entry (CPOE), there are fewer medications given to the patients: 1,9 per hospital record. The drugs for accompanying and chronic diseases, which are not prescribed via the Hospital Pharmacy, are entered in the discharge letters as free text. Thus, much information about the treatment is presented as unstructured descriptions. Similar comments can be made concerning the clinical examinations and lab tests: often the patients bring their test results on paper; the practice is not to repeat recent tests. Whenever the clinical test is made in USHATE, the lab data are stored automatically in the Laboratory Information System (LIS) which is a part of the HIS. However the values of clinical tests, made outside USHATE, are re-typed to the discharge letter for all examinations that are relevant to the present hospitalisation. Another particularity is due to the fact that reimbursements by the Bulgarian National Health Fund are based on clinical pathways; often the USHATE experts diagnose formally the principal disease which is sufficient to associate the patient to the desired pathway. But the hospitalised patients usually have specific, complex history cases. Statistical observations show that the average number of diagnoses per patient is 4,32 in contrast of only 1 diagnose recorded in HIS. Thus accompanying illnesses and complications, which are not formally encoded by the USHATE HIS, might be enumerated in the text paragraphs of the discharge letters. In this way the integrated picture of the patient diseases, history, status, lab data and treatment is presented only in the discharge letters of USHATE patients.

Therefore the secondary use of the hospital PRs in USHATE requires: (i) obligatory text analysis -to identify in the text the drugs, diagnoses, values of clinical tests, lab data as well as patient status attributes; (ii) strategies for integration of the various information fragments and (iii) maintenance of incomplete informationincluding timing of various events which are not precisely dated in the free text.

Specific Text Features of Bulgarian Discharge Letters

Discharge letters in all Bulgarian hospitals have mandatory structure, which is published in the Official State Gazette within the legal Agreement between the Bulgarian Medical Association and the National Health Insurance Fund [START_REF]National Framework Contract between the National Health Insurance Fund, the Bulgarian Medical Association and the Bulgarian Dental Association[END_REF]. The letters contain: (i) personal data; (ii) diagnoses; (iii) anamnesis; (iv) patient status; (v) lab data; (vi) medical examiners comments; (vii) discussion; (viii) treatment; and (ix) recommendations. This structure provides appropriate contextualization of the extracted entities although it is often neglected because the authoring experts merge sections, omit empty sections, skip subsections, enter incomplete information and so on. Fig. 1 shows the percentage of existing sections in a training corpus of 1,300 anonymised PRs. After our studies in literature dealing with biomedical NLP for other languages, we note that the relatively established format of Bulgarian discharge letters is a significant advantage in the development of automatic analysis for Bulgarian.

Figure 1. Availability of discharge letter zones

Finally we briefly present some specific particularities of the Bulgarian medical language. In the hospital PRs, medical terminology is recorded in both Bulgarian and/or Latin language. There is no preferred language for the terminology so the two forms are used like synonyms. Sometimes Latin terms are written by Cyrillic letters especially when the medical expert prefers to avoid keyboard switching. In general the mixture of Latin and Bulgarian terms is traditionally established and commonly accepted, including in official documents. In this way the automatic identification of a term in the hospital PR texts is a tricky task which requires more than a simple string match. Fig. 2 shows some original excerpts of PR diagnoses: Latin names of diseases are transliterated by Cyrillic letters but alternatively might be given in Latin as well. The measurement units of clinical test are often entered with Latin symbols.

Figure 2. Excerpts of hospital PRs in USHATE 4 Integration of Entities Encountered in Hospital PRs

For our PSIP experiment, all entities automatically extracted from the hospital PRs should be integrated as complementary data to the information, contained in the HIS (including the LIS, the CPOE and the Hospital Pharmacy). Therefore we need to design the time framework which unifies and harmonises all events encountered in every particular discharge letter.

The dates (beginning and end of the hospital stay) are set in the HIS of USHATE for each patient. The admission day is referred to as 'Day 0'. All drug prescriptions and lab data, stored in the HIS, are marked by respective dates and hours within the Svetla Boytcheva1, Galia Angelova1, Zhivko Angelov1, Dimitar Tcharaktchiev2, Hristo Dimitrov2 hospital stay interval so the time markers of these medication and examination events are delivered by the HIS. The clinical treatment usually starts at Day 1, so we have made experiments to discover automatically the drugs taken at Day 0. Only the text paragraphs in the Anamnesis were considered because this is the PR zone where drugs are listed, with comments that some drugs are taken at the hospitalisation moment. Dosage is often specified explicitly as definition of the admission medication status. The experiment was carried out with the corpus of 6,200 PRs and all 1,537 drugs in our lexicons. In general there are many drugs presented in the Case history (30,190 drug name occurrences in 6,194 Anamneses). Some 4,088 occurrences (13,5%) were automatically recognised as "current medication" in 3,191 PRs, which means that 51% of the PRs contain explicit statements concerning the "current medication" in the Anamnesis text. More than one drug can be specified as a "current" one.

Most often the text expression, signalling the treatment at Day 0, is the phrase "at the admission" (при постъпването). This phrase occurs with slight variations in 2,122 PRs (34%). On average 25% of all drugs in the Case history are recognised as "Day 0 medication". There are PRs, however, for which up to 45% of the medication events listed in the Case history are "current". A sample PR excerpt is: "therapy at the admission novorapid 14+14+14E, insulatard 24E at 22h" (терапия при постъпването новорапид 14+14+14E, инсулатард 24E в 22ч)".

The second preferred text expression which signals "Day 0 medication" is "at the moment" (в момента... ). It occurs in 908 PRs from the test set of 6,200 PRs; in 703 PRs (11%) the phrase refers to explicitly specified drugs in the local context. These 703 cases were encountered after manual inspection of automatically prepared summarising sheets for occurrences of drug names in the Anamneses. On average, 14,5% of all drugs in the 703 PRs Case history are recognised as "Day 0 medication". Sample usages of this phrase are: "at the moment takes dostinex 2x2 t weekly" (в момента на достинекс 2х2 т седмично) and "at the moment treated with physiotens 0,4mg, lorista 1t, isoptin 2x80mg with satistactory effect".

The above-listed drugs are considered as Day 0 only after careful training of the extracting components and evaluation of the erroneous recognitions. Please note that the expressions "at the admission" and "at the moment" can be used in other phrases as well, like "therapy at the admission: none", "at the moment without complains" and "aged X, at the moment 93 kg".

As an example of integrated entities, we present the Patient Case with ID 26137: (i) the principle diagnose in the USHATE HIS is E668 'Other obesity', and the extractor discovers in addition E898 'Postprocedural adrenocortical (-medullary) hypofunction' and E289 'Other ovarian dysfunction'; (ii) there is only one entry found in the Hospital Pharmacy (Metamizole) and the drug extractor delivered eight records for taking Metfodiab for eight days; (iii) there are 22 lab data entries in the USHATE HIS but the mining component adds seven more values at Day 0 mostly for hormones.

Automatic Extraction of ICD-10 Codes to Diagnoses

The PRs in our corpus often contain diagnoses expressed as free text (despite the fact that the present USHATE HIS offers menu choice for ICD-10 diagnoses). For the corpus of 6,200 PRs, some 495 different ICD-10 codes were identified in the PR zones Diagnoses. Fortunately the zones themselves are presented as major discharge letter paragraphs and can be recognised automatically with almost 100% accuracy. However, in the PR text we find terms, phrases and paraphrases which might differ significantly from the ICD disease labels. The number of diagnoses per patient varies from 1 to about 30; most PRs contain from one to seven diagnoses. The nomenclature ICD-10 with Bulgarian terms is used as an external resource and lexicon for this module.

The main obstacle for the automatic assignment of ICD codes is that the correspondence between the PR diagnoses and ICD-10 disease names is "many to many". There are generally formulated phrases in the PR text which correspond to several ICD-10 diagnoses (like e.g. hypothyroidism). Some phrases can be matched exactly to one ICD-10 disease (for instance, diabetic polyneuropathy). Major difficulties for the linguistic analysis are caused by transliterations and paraphrases: (i) there are Latin names of the illness, transliterated by Cyrillic letters, which differs from the Bulgarian labels included in the ICD-10, for instance, 'Диабетес мелитус' (Diabetes Mellitus) in the PR text vs 'Захарен диабет' in ICD; (ii) the PR texts contain syntactical paraphrases of disease names, often with mixture of Bulgarian-Latin writing, and/or join of various diseases and symptoms in conjunctive nominal phrase, for instance 'полиневропатия ет нефропатия диабетика в стадий на микроалбуминурия' (polyneuropathy et neuropathy diabetica in the stage of microalbuminuria); (iii) the PR texts contain sophisticated syntactic constructions, e.g. splitting the components of complex ICD-10 terms and presenting them into various levels of a joint syntactic structures.

For solving this task a machine learning algorithm was especially designed and implemented. A smaller training corpus of 600 PRs was used for manual association of corresponding ICD-10 codes to diagnoses as they are presented in the text. Further the algorithm is automatically trained on 1,300 PRs. More details about the automatic coding of ICD-10 diagnoses in Bulgarian are given in [START_REF] Tcharaktchiev | Completion of Structured Patient Descriptions by Semantic Mining[END_REF].

Automatic Extraction of Drugs

The list of drugs in the USHATE's Hospital Pharmacy is supported with Bulgarian drug names even for drugs produced abroad (in this case the foreign words are transliterated by Cyrillic letters). However, the official list of registered drugs, published by the Bulgarian Drug Agency [START_REF]Bulgarian Drug Agency[END_REF], contains the ATC codes and the drug names in Latin alphabet even for drugs produced in Bulgaria. It is worth mentioning that all the Application instructions in the Bulgarian Drug Agency site [START_REF]Bulgarian Drug Agency[END_REF] are written in Bulgarian and the drug names are given there by Cyrillic letters. Note that the ATC classification is not available for drug names in Bulgarian language; therefore we have selected about 2000 drug names (covering the drugs relevant for the USHATE patients in the PSIP corpus) and have (semi-)manually assigned ATC codes to drug names in Bulgarian. In the process of resource compilation for the corpus of 6,200 discharge letters, it became clear that the USHATE patients take 355 drugs during the hospitalisation period, which are not prescribed via the Hospital Pharmacy. The drug extractor is focused on identification of these drugs when they are taken during the hospitalisation period. The information extraction task is accomplished by a rule-based algorithm that uses over 50 regular expressions for drug events recognition.

Recognising drug names is based on string matching which is difficult due to many reasons. Drugs have various names that might be referred to in the PR texts: e.g. brand and generic names. There are variants in writing names, especially for names consisting of several strings. Actually multi-word drug names might occur in the PR text as a single wordform because the other name parts are omitted. Additionally, drug names in the PR might be written with Cyrillic letters, for Bulgarian names and transliterated Latin names, and with Latin alphabet. In order to capture all names during the text processing phase, we need a comprehensive vocabulary of drug names in both languages and both alphabets (as well as the ATC codes).

Due to the highly inflectional Bulgarian language, some drug names might appear in the PR texts with various wordforms. This lexical variety, which prevents the exact match of drug names from the PR texts to the lexicon items, occurs mostly for plural and singular forms. In 1,300 PRs, some 43 grammatical forms of 23 drug names were automatically found by our morphological analysers. Another obstacle in string matching might be due to the typos. In principle spelling errors prevent the correct recognition of all text entities in the PR texts (and need to be tackled by automatic correctors). For 1,300 PRs, 4,042 drug name occurrences of 239 drugs were automatically identified. Some 100 PRs were manually studied for typos. The erroneous occurrences are 59 (1,5%) and the errors appeared in the names of 21 drugs.

The lexicons of our drug extracting component contain 1,182 drug names, which are prescribed via the USHATE Hospital Pharmacy, and another 355 drugs that occur in the USHATE hospital PRs but are not prescribed via the Hospital Pharmacy (the latter are taken by the patients to cure additional/chronic illnesses). Tokens which are part of drugs names occur in the whole PR text; in fact drug names participate even in the zone Diagnoses (e.g. 'deficiency of Vitamin D'). In this way our procedure for automatic recognition of drug names finds words, signaling potential drug treatments, everywhere in the PRs. More details about the drug extraction component can be found in [START_REF] Boytcheva | Shallow Medication Extraction from Hospital Patient Records[END_REF]. The contextualisation of medication events (i.e. to recognise the drugs admitted during the hospitalisation period) is further discussed in [START_REF] Boytcheva | Contenxtualisation in Automatic Extraction of Drugs from Hospital Patient Records[END_REF]. In section 5 we present new evaluation results concerning the extraction of "current" medication events from the unstructured texts of the PR Anamnesis.

Automatic Extraction of Values of Clinical Tests and Lab Data

Fig. 1 shows that the lab data are presented in a specific PR zone which is practically always available and can be automatically identified with almost 100% accuracy despite the variety of section titles and subtitles. The values are listed without predetermined order, using measurement units and their abbreviations both in Bulgarian and Latin. These measurement units are compliant to the LOINC (Logical Observation Identifiers Names and Codes) [20] classification and often enable the recognition of the corresponding indicator which might be referred to without explicit and standardised indicator name. The lab data extractor identifies the tested attribute and its value. The units and reference intervals are desirable features to recognise, and the time, condition and explanation of further details are optional features. The extraction algorithm is based on rules and pattern matching; the rules are acquired after manual training on 1,300 PRs and recorder in different versions to cope with various delimiters and blank spaces, which might occur in the text [START_REF] Tcharaktchiev | Completion of Structured Patient Descriptions by Semantic Mining[END_REF].

Evaluation Results and Discussion

The automatic extractors were run on 6,200 anonymised PRs. The accuracy for the automatic extraction of diagnoses, drugs, and clinical tests data is presented in Table 1. These events were integrated with the HIS data to constitute the PSIP repository [START_REF] Tcharaktchiev | Completion of Structured Patient Descriptions by Semantic Mining[END_REF]. Recently the repository was used for discovery of USHATE-specific ADEs. The medication events occurring during the hospitalisation are recognised with fscore 90.17% for 355 drugs [START_REF] Boytcheva | Contenxtualisation in Automatic Extraction of Drugs from Hospital Patient Records[END_REF]. The over-generation is 6%, i.e. some drugs are wrongly classified as "admitted during the hospital stay". These erroneous decisions are made for phrases like "… to continue the treatment with drug X …" in the Debate section, which communicate incomplete information and are ambiguous for human being as well. In all cases of overlapping descriptions the HIS data are preferred as more exact and reliable. In general the automatically extracted entities have mostly statistical meaning in the procedure of data analysis and ADE discovery for USHATE.

Extracted entities from the

Figure 4. Integration of the drug extractor into on-line validation interface in USHATE

Recently an experimental validation of the PSIP Scorecards [START_REF] Marcilly | Design of Adverse Drug Events-Scorecards[END_REF][START_REF] Koutkias | Constructing Clinical Decision Support Systems for Adverse Drug Event Prevention: A Knowledge-based Approach[END_REF] in USHATE has been accomplished. Actually the extractors, developed for the Bulgarian PR texts, provided interoperability between the USHATE PRs and the PSIP data formats: once structured information is extracted from the free texts, it can be recorded in various databases using ATC and ICD codes. The validating doctors were quite positive about the experimental integration of the drug extractor as an on-line analyser in the HIS (see Fig. 4). It delivers automatically the drugs taken at Day 0 whenever the Anamnesis is recorder in the HIS, which provides structured data in a convenient format that can be further used for prescriptions. Validating the PSIP approach, some situations at risk were found in the experimental USHATE repository (hypo-and hyperkalemia, hypoand hyperglycemia, leucopenia, renal failure). The integrated repository of patient data, prepared using the technologies presented in this article, is an example of resource which explicates the potential of secondary EHR use.

Conclusion

This article presents a research effort in automatic extraction of structured information from hospital PRs, performed in order to integrate a repository for experimental discovery of ADEs. We have described our empirical strategy to assign time anchors to the entities encountered in the PR free texts. The integrated repository for USHATE is relatively small but relatively sophisticated as it comprises the HIS data as well as the results of four automatic extractors.

The information extraction approach is to identify entities of interest and to implement software tools which perform partial analysis of the text fragments that contain words of interest. The remaining part of the PR texts is disregarded. Our experience shows that via a rapid development process, one can achieve good performance in several automatic extraction tasks within 2-3 years. To some extent the extraction accuracy reported here is implied by the established structure of the discharge letters in Bulgarian hospitals. The negative results (including overgeneration) are an inevitable aspect of the NLP performance but they are partly due to the inconsistency, incompleteness and fragmentariness of the medical documentation per se; these shortcomings become obvious in the computer age when ambitious goals like secondary use of EHR data are set. The false positive indications might be dangerous for further use but in our case the small percentage of false positive entities is statistically insignificant and practically negligible (we note that human recognition of medical entities in clinical narratives and data preparation might also include some erroneous choices).

We also note the stable medical tradition to type in textual descriptions even when the HIS stores the prescriptions. Medical experts document carefully information about the therapy and its changes during the hospital stay. These practices make the NLP technology a valuable component in the secondary use of EHR data.

Acknowledgment

The research tasks leading to these results have received funding from the EC's FP7 ICT under grant agreement n° 216130 PSIP (Patient Safety through Intelligent Procedures in Medication) as well as from the Bulgarian National Science Fund under

. . .

 . Диабетес мелитустипус 1. Ретинопатиа диабетика пролиферанс. Статус пост ALC. Полиневропатиа диабетика. Хипертония артериалис гр. I. ... ... Kонсултация с офталмолог: VOD= 0,8; VOS= 0,6-0,7; двуочно 0,9-1,0 със собствена корекция. Angiosclerosis vas. retinae hypertonica. Retinopathia diabetica simplex. макули без рефлекс...

Fig. 3

 3 illustrates the association of time anchors to the entities, extracted from the PR text by the four extractors in our experiment: (i) Diagnoses extraction module -automatically extracts diagnoses from the PR zone "Diagnoses", associates the corresponding ICD-10 codes and stores them in the PSIP repository; (ii) Drug events extraction module -automatically extracts drug names, recognised as "current treatment of accompanying diseases", and their dosage. The module automatically associates ATC codes to these drugs. In case they are not prescribed by the Hospital Pharmacy, the extractor relates them to Day 0 (and for chronic diseases like e.g. hypertonia, to each day spent in the hospital day). Then these drugs are stored for the current patient in the PSIP repository; (iii) Clinical data extraction module -automatically analyses the clinical examinations and tests, made outside USHATE (e.g. hormonal tests), anchors the to Day 0 and stores them in the PSIP repository; (iv) Status extraction module -automatically extracts the patient status' attributes, which by default reflect the patient characteristics at Day 0.

Figure 3 .

 3 Figure 3. Integration of data and events stored in the Hospital Information System of USHATE and in the free texts of discharge letters

Table 1 . Number of extracted items from 6,200 PRs

 1

		PRs text	Precision	Recall	F-Measure
	Diagnoses	26 826	97.30%	74.69%	84.50%
	Drug names	160 892	97.28%	99.59%	98.42%
	Laboratory Test Results	114 441	98.20%	99.99%	99.04%